fork(1) download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<cassert>
  5. #define MAXN 200000
  6. #define NEUTRAL -2
  7. using namespace std;
  8.  
  9. int t[4 * MAXN];
  10. int a[MAXN];
  11.  
  12. void build(int v, int l, int r) {
  13.     if (l + 1 == r) {
  14.         t[v] = l;
  15.         return;
  16.     }
  17.     int m = (l + r) / 2;
  18.     build(2 * v, l, m);
  19.     build(2 * v + 1, m, r);
  20.     if (a[t[2 * v]] >= a[t[2 * v + 1]]) {
  21.         t[v] = t[2 * v];
  22.     } else {
  23.         t[v] = t[2 * v + 1];
  24.     }
  25. }
  26.  
  27. void update(int v, int l, int r, int pos, int x) {
  28.     if (l + 1 == r) {
  29.         a[pos] = x;
  30.         return;
  31.     }
  32.     int m = (l + r) / 2;
  33.     if (pos < m) {
  34.         update(2 * v, l, m, pos, x);
  35.     } else {
  36.         update(2 * v, m, r, pos, x);
  37.     }
  38.     if (a[t[2 * v]] >= a[t[2 * v + 1]]) {
  39.         t[v] = t[2 * v];
  40.     } else {
  41.         t[v] = t[2 * v + 1];
  42.     }
  43. }
  44.  
  45. int find_nearest(int v, int l, int r, int i, int x) {
  46.     if (r <= i || a[t[v]] < x) {
  47.         return NEUTRAL;
  48.     }
  49.     if (l + 1 == r) {
  50.         return t[v];
  51.     }
  52.     int m = (l + r) / 2;
  53.     int ans1 = -2, ans2 = -2;
  54.     if (a[t[2 * v]] >= x) {
  55.         ans1 = find_nearest(2 * v, l, m, i, x);
  56.     }
  57.     if (a[t[2 * v + 1]] >= x) {
  58.         ans2 = find_nearest(2 * v + 1, m, r, i, x);
  59.     }
  60.     if (ans1 != -2) {
  61.         return ans1;
  62.     } else {
  63.         return ans2;
  64.     }
  65. }
  66. int main() {
  67.     //assert(freopen("nearandmore.in", "r", stdin));
  68.     //assert(freopen("nearandmore.out", "w", stdout));
  69.     int N, M;
  70.     cin >> N >> M;
  71.     for (int i = 0; i < N; ++i) {
  72.         cin >> a[i];
  73.     }
  74.     build(1, 0, N);
  75.     for (int i = 0; i < M; ++i) {
  76.         int t, ind, x;
  77.         cin >> t >> ind >> x;
  78.         if (t == 0) {
  79.             update(1, 0, N, ind - 1, x);
  80.         } else {
  81.             cout << find_nearest(1, 0, N, ind - 1, x) + 1 << '\n';
  82.         }
  83.     }
  84. }
Success #stdin #stdout 0s 4392KB
comments (?)
stdin
copy 
5 4
3 0 5 4 1
0 4 4
1 4 3
0 3 5
1 1 4
stdout
copy 
4
3
https://ideone.com/oDOJdF
language:
C++14 (gcc 8.3)
created:
4 years 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!