fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int inf  = 1e9 + 7;
  6. const int maxN = 1e5 + 7;
  7.  
  8. int n, m;
  9. int a[maxN];
  10. multiset <int> st[4 * maxN];
  11.  
  12. void build(int id, int l, int r) {
  13.     if (l == r) {
  14.         st[id].insert(a[l]);
  15.         return;
  16.     }
  17.     int mid = l + r >> 1;
  18.     build(2 * id, l, mid);
  19.     build(2 * id + 1, mid + 1, r);
  20.  
  21.     st[id] = st[2 * id + 1];
  22.     for (auto x : st[2 * id]) st[id].insert(x);
  23. }
  24.  
  25. void update(int id, int l, int r, int i, int old, int val) {
  26.     if (l > i || r < i) return;
  27.     if (l == r) {
  28.         st[id].clear();
  29.         st[id].insert(val);
  30.         return;
  31.     }
  32.     int mid = l + r >> 1;
  33.     update(2 * id, l, mid, i, old, val);
  34.     update(2 * id + 1, mid + 1, r, i, old, val);
  35.     st[id].erase(st[id].find(old));
  36.     st[id].insert(val);
  37. }
  38.  
  39. int get(int id, int l, int r, int u, int v, int k) {
  40.     if (l >  v || r <  u) return inf;
  41.     if (l >= u && r <= v) {
  42.         auto it = st[id].lower_bound(k);
  43.         if (it == st[id].end()) return inf;
  44.         return *it;
  45.     }
  46.  
  47.     int mid = l + r >> 1;
  48.     int get1 = get(2 * id, l, mid, u, v, k);
  49.     int get2 = get(2 * id + 1, mid + 1, r, u, v, k);
  50.     return min(get1, get2);
  51. }
  52.  
  53. int main() {
  54.     cin >> n >> m;
  55.     for (int i = 1; i <= n; ++i) cin >> a[i];
  56.     build(1, 1, n);
  57.  
  58.     while (m--){
  59.         int type, l, r, k;
  60.         cin >> type;
  61.         if (type == 1) {
  62.             cin >> l >> k;
  63.             update(1, 1, n, l, a[l], k);
  64.             a[l] = k;
  65.         }
  66.         else {
  67.             cin >> l >> r >> k;
  68.             int ans = get(1, 1, n, l, r, k);
  69.             cout << ((ans == inf) ? -1 : ans) << '\n';
  70.         }
  71.     }
  72. }
Success #stdin #stdout 0.01s 22276KB
comments (?)
stdin
copy 
5 5
4 0 3 1 7
2 8
2 10
1 3 10
2 0
2 7
stdout
copy 
-1
-1
-1
-1
https://ideone.com/DKLEkO
language:
C++14 (gcc 8.3)
created:
20 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!