fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7.  
  8. #define saleh                         \
  9.     ios_base::sync_with_stdio(false); \
  10.     cin.tie(nullptr);
  11. #define ll long long
  12.  
  13. int n, m;
  14.  
  15. struct node
  16. {
  17.     int val;
  18.  
  19.     node(int x)
  20.     {
  21.         val = x;
  22.     }
  23. };
  24.  
  25. struct segTree
  26. {
  27.     int size = 1;
  28.     vector<int> segData;
  29.  
  30.     void build(int n)
  31.     {
  32.         while (size < n)
  33.         {
  34.             size *= 2;
  35.         }
  36.         segData.resize(2 * size);
  37.     }
  38.  
  39.     void build(vector<int> &v, int x, int lx, int rx)
  40.     {
  41.         if (rx - lx == 1)
  42.         {
  43.             if (lx < v.size())
  44.             {
  45.                 segData[x] = (v[lx]);
  46.             }
  47.             return;
  48.         }
  49.         int mid = (lx + rx) / 2;
  50.         build(v, 2 * x + 1, lx, mid);
  51.         build(v, 2 * x + 2, mid, rx);
  52.         segData[x] = max(segData[2 * x + 1], segData[2 * x + 2]);
  53.     }
  54.  
  55.     void build(vector<int> &v)
  56.     {
  57.         build(v, 0, 0, size);
  58.     }
  59.  
  60.     void change(int i, int v, int x, int lx, int rx)
  61.     {
  62.         if (rx - lx == 1)
  63.         {
  64.  
  65.             segData[x] = v;
  66.             return;
  67.         }
  68.         int mid = (lx + rx) / 2;
  69.         if (i < mid)
  70.         {
  71.             change(i, v, 2 * x + 1, lx, mid);
  72.         }
  73.         else
  74.         {
  75.             change(i, v, 2 * x + 2, mid, rx);
  76.         }
  77.         segData[x] = max(segData[2 * x + 1], segData[2 * x + 2]);
  78.     }
  79.  
  80.     void change(int i, int v)
  81.     {
  82.         change(i, v, 0, 0, size);
  83.     }
  84.  
  85.     int find(int v, int l, int x, int lx, int rx)
  86.     {
  87.         if (rx - lx == 1)
  88.         {
  89.             if (segData[x] >= v && lx >= l)
  90.                 return lx;
  91.             else
  92.                 return n;
  93.         }
  94.         int mid = (lx + rx) / 2;
  95.         int leftpart = n, rightpart = n;
  96.         if (v <= segData[2 * x + 1] && l<mid)
  97.         {
  98.             leftpart = find(v, l, 2 * x + 1, lx, mid);
  99.         }
  100.         if (v <= segData[2 * x + 2])
  101.         {
  102.             rightpart = find(v, l, 2 * x + 2, mid, rx);
  103.         }
  104.         return min(leftpart, rightpart);
  105.     }
  106.  
  107.     int find(int v, int l)
  108.     {
  109.         return find(v, l, 0, 0, size);
  110.     }
  111. };
  112.  
  113. void solve()
  114. {
  115.  
  116.     cin >> n >> m;
  117.  
  118.     segTree segment;
  119.     segment.build(n);
  120.     vector<int> v(n);
  121.     for (auto &i : v)
  122.     {
  123.         cin >> i;
  124.     }
  125.  
  126.     segment.build(v);
  127.  
  128.     while (m--)
  129.     {
  130.         int op;
  131.         cin >> op;
  132.         if (op == 1)
  133.         {
  134.             int ind, v;
  135.             cin >> ind >> v;
  136.             segment.change(ind, v);
  137.         }
  138.         else
  139.         {
  140.             int x, l;
  141.             cin >> x >> l;
  142.             int ans = segment.find(x, l);
  143.             cout << (ans != n ? ans : -1) << endl;
  144.         }
  145.     }
  146. }
  147.  
  148. int main()
  149. {
  150.     saleh;
  151.     solve();
  152. }
  153.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pUShZL
language:
C++ (gcc 8.3)
created:
3 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!