fork(1) download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<cassert>
  5. #define MAXN 5
  6. #define NEUTRAL -2
  7. using namespace std;
  8. int N, M;
  9. int t[4 * MAXN];
  10. int a[MAXN];
  11. int a2[MAXN];
  12.  
  13. void build(int v, int l, int r) {
  14.     if (l + 1 == r) {
  15.         t[v] = l;
  16.         return;
  17.     }
  18.     int m = (l + r) / 2;
  19.     build(2 * v, l, m);
  20.     build(2 * v + 1, m, r);
  21.     if (a[t[2 * v]] >= a[t[2 * v + 1]]) {
  22.         t[v] = t[2 * v];
  23.     } else {
  24.         t[v] = t[2 * v + 1];
  25.     }
  26. }
  27.  
  28. void update(int v, int l, int r, int pos, int x) {
  29.     if (l + 1 == r) {
  30.         a[pos] = x;
  31.         return;
  32.     }
  33.     int m = (l + r) / 2;
  34.     if (pos < m) {
  35.         update(2 * v, l, m, pos, x);
  36.     } else {
  37.         update(2 * v, m, r, pos, x);
  38.     }
  39.     if (a[t[2 * v]] >= a[t[2 * v + 1]]) {
  40.         t[v] = t[2 * v];
  41.     } else {
  42.         t[v] = t[2 * v + 1];
  43.     }
  44. }
  45.  
  46. int find_nearest(int v, int l, int r, int i, int x) {
  47.     if (r <= i || a[t[v]] < x) {
  48.         return NEUTRAL;
  49.     }
  50.     if (l + 1 == r) {
  51.         return t[v];
  52.     }
  53.     int m = (l + r) / 2;
  54.     int ans1 = -2, ans2 = -2;
  55.     if (a[t[2 * v]] >= x) {
  56.         ans1 = find_nearest(2 * v, l, m, i, x);
  57.     }
  58.     if (a[t[2 * v + 1]] >= x) {
  59.         ans2 = find_nearest(2 * v + 1, m, r, i, x);
  60.     }
  61.     if (ans1 != -2) {
  62.         return ans1;
  63.     } else {
  64.         return ans2;
  65.     }
  66. }
  67.  
  68. vector<vector<int>>input;
  69. void generate() {
  70.     N = rand() % MAXN + 1;
  71.     M = rand() % MAXN + 1;
  72.     for (int i = 0; i < N; ++i) {
  73.         a[i] = rand() % MAXN;
  74.         a2[i] = a[i];
  75.     }
  76.     // 0 - set, 1 - get
  77.     for (int i = 0; i < M; ++i) {
  78.         input.push_back({ rand() % 2, rand() % N + 1, rand() % MAXN + 1 });
  79.     }
  80. }
  81. vector<int> DO_ans, SLOW_ans;
  82. void DO_version() {
  83.     //assert(freopen("nearandmore.in", "r", stdin));
  84.     //assert(freopen("nearandmore.out", "w", stdout));
  85.     build(1, 0, N);
  86.     for (int i = 0; i < M; ++i) {
  87.         int t = input[i][0], ind = input[i][1], x = input[i][2];
  88.         if (t == 0) {
  89.             update(1, 0, N, ind - 1, x);
  90.         } else {
  91.             DO_ans.push_back(find_nearest(1, 0, N, ind - 1, x) + 1);
  92.         }
  93.     }
  94. }
  95.  
  96. void SLOW_version() {
  97.     for (int i = 0; i < M; ++i) {
  98.         int t = input[i][0], ind = input[i][1] - 1, x = input[i][2];
  99.         if (t == 0) {
  100.             a2[ind] = x;
  101.         }
  102.         else {
  103.             for (int j = ind; j < N; ++j) {
  104.                 if (a2[j] >= x) {
  105.                     SLOW_ans.push_back(j + 1);
  106.                     break;
  107.                 }
  108.                 if (j == N - 1) {
  109.                     SLOW_ans.push_back(-1);
  110.                 }
  111.             }
  112.         }
  113.     }
  114. }
  115.  
  116. int main() {
  117.     while (true) {
  118.         input = {};
  119.         generate();
  120.         cout << "IT'S N AND M: " << N << " " << M << '\n';
  121.         DO_ans = {};
  122.         SLOW_ans = {};
  123.         DO_version();
  124.         SLOW_version();
  125.         if (SLOW_ans != DO_ans) {
  126.             for (int i = 0; i < N; ++i) {
  127.                 cout << a[i] << " ";
  128.             }
  129.             cout << '\n';
  130.             for (auto a : input) {
  131.                 for (auto out : a) {
  132.                     cout << out << " ";
  133.                 }
  134.                 cout << '\n';
  135.             }
  136.             break;
  137.         }
  138.         cout << "###################################################################\n";
  139.     }
  140. }
Success #stdin #stdout 0s 4392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
IT'S N AND M: 4 2
###################################################################
IT'S N AND M: 1 5
###################################################################
IT'S N AND M: 5 3
###################################################################
IT'S N AND M: 4 5
###################################################################
IT'S N AND M: 5 4
###################################################################
IT'S N AND M: 4 2
###################################################################
IT'S N AND M: 5 5
###################################################################
IT'S N AND M: 1 5
###################################################################
IT'S N AND M: 5 5
###################################################################
IT'S N AND M: 5 4
###################################################################
IT'S N AND M: 2 3
###################################################################
IT'S N AND M: 1 4
###################################################################
IT'S N AND M: 1 5
###################################################################
IT'S N AND M: 1 1
###################################################################
IT'S N AND M: 3 3
###################################################################
IT'S N AND M: 4 1
###################################################################
IT'S N AND M: 4 1
###################################################################
IT'S N AND M: 2 3
###################################################################
IT'S N AND M: 4 2
###################################################################
IT'S N AND M: 5 2
###################################################################
IT'S N AND M: 5 2
###################################################################
IT'S N AND M: 5 5
###################################################################
IT'S N AND M: 3 1
###################################################################
IT'S N AND M: 2 2
###################################################################
IT'S N AND M: 3 5
###################################################################
IT'S N AND M: 4 2
###################################################################
IT'S N AND M: 5 4
###################################################################
IT'S N AND M: 4 2
###################################################################
IT'S N AND M: 2 4
###################################################################
IT'S N AND M: 1 3
###################################################################
IT'S N AND M: 5 4
###################################################################
IT'S N AND M: 5 2
###################################################################
IT'S N AND M: 5 4
###################################################################
IT'S N AND M: 2 5
###################################################################
IT'S N AND M: 2 5
###################################################################
IT'S N AND M: 3 1
###################################################################
IT'S N AND M: 3 2
###################################################################
IT'S N AND M: 5 1
###################################################################
IT'S N AND M: 5 2
###################################################################
IT'S N AND M: 4 4
###################################################################
IT'S N AND M: 5 4
###################################################################
IT'S N AND M: 1 3
###################################################################
IT'S N AND M: 2 3
###################################################################
IT'S N AND M: 2 5
###################################################################
IT'S N AND M: 5 5
###################################################################
IT'S N AND M: 4 1
###################################################################
IT'S N AND M: 2 4
###################################################################
IT'S N AND M: 5 3
###################################################################
IT'S N AND M: 4 1
###################################################################
IT'S N AND M: 1 5
###################################################################
IT'S N AND M: 3 2
###################################################################
IT'S N AND M: 3 2
###################################################################
IT'S N AND M: 3 4
###################################################################
IT'S N AND M: 5 4
###################################################################
IT'S N AND M: 3 1
###################################################################
IT'S N AND M: 4 4
###################################################################
IT'S N AND M: 2 5
###################################################################
IT'S N AND M: 3 4
###################################################################
IT'S N AND M: 2 2
###################################################################
IT'S N AND M: 1 5
###################################################################
IT'S N AND M: 2 5
###################################################################
IT'S N AND M: 5 2
###################################################################
IT'S N AND M: 4 3
###################################################################
IT'S N AND M: 4 1
###################################################################
IT'S N AND M: 5 1
###################################################################
IT'S N AND M: 2 5
###################################################################
IT'S N AND M: 2 4
###################################################################
IT'S N AND M: 3 3
###################################################################
IT'S N AND M: 3 3
###################################################################
IT'S N AND M: 2 5
###################################################################
IT'S N AND M: 2 5
###################################################################
IT'S N AND M: 3 4
###################################################################
IT'S N AND M: 1 3
###################################################################
IT'S N AND M: 1 3
###################################################################
IT'S N AND M: 4 4
###################################################################
IT'S N AND M: 5 5
###################################################################
IT'S N AND M: 5 3
###################################################################
IT'S N AND M: 1 4
###################################################################
IT'S N AND M: 5 5
###################################################################
IT'S N AND M: 1 1
###################################################################
IT'S N AND M: 4 1
###################################################################
IT'S N AND M: 5 5
###################################################################
IT'S N AND M: 1 2
###################################################################
IT'S N AND M: 4 3
###################################################################
IT'S N AND M: 4 3
###################################################################
IT'S N AND M: 3 3
2 3 1 
0 3 1 
0 2 3 
1 2 2
https://ideone.com/kc0M3m
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!