oj.uz

Submission #337625

# Submission time Handle Problem Language Result Execution time Memory
337625 2020-12-21T09:45:15 Z boykut Simple game (IZhO17_game) C++14
100 / 100
 484 ms 19584 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1000010;

int mas[4 * N], be[4 * N];

void push(int v, int l, int r) {
   if (be[v]) {
      mas[v] += (r - l + 1) * be[v];
      if(l != r){
         be[v + v] += be[v];
         be[v + v + 1] += be[v];
      }
      be[v] = 0;
   }
}
int get(int v, int l, int r, int ql, int qr) {
   push(v, l, r);
   if (l > qr || r < ql)
      return 0;
   if (ql <= l && r <= qr)
      return mas[v];
   int mid = (l + r) / 2;
   return get(v + v, l, mid, ql, qr) + get(v + v + 1, mid + 1, r, ql, qr);
}
void update(int v, int l, int r, int ql, int qr, int val) {
   push(v, l, r);
   if(l > qr || r < ql)
      return;
   if (ql <= l && r <= qr) {
      mas[v] += (r-l+1)*val;
      if (l != r) {
         be[v + v] += val;
         be[v + v + 1] += val;
      }
      return;
   }
   int mid = (l + r) / 2; 
   update(v + v, l, mid, ql, qr, val);
   update(v + v + 1, mid + 1, r, ql, qr, val);
   mas[v] = mas[v + v] + mas[v + v + 1];
}

signed main() {
   ios::sync_with_stdio(0);
   cin.tie(0);
   
   int n, m;
   cin >> n >> m;
   
   int h[n];
   
   for (int i = 0; i < n; i++) {
      cin >> h[i];
      if (i) {
         int left = h[i], right = h[i - 1];
         if (left > right) swap(left, right);
         update(1, 1, N, left, right, 1);
      }
   }
   
   for (int test = m; test--;) {
      int x;
      cin >> x;
      
      if (x == 1) {
         int pos, val;
         cin >> pos >> val;
         pos--;
         
         auto inc = [&](int l, int r, int val) -> void{
            if (l > r) swap(l, r);
            update (1, 1, N, l, r, val);
         };
         
         if (pos) {
            inc(h[pos], h[pos - 1], -1);
         }
         if (pos + 1 < n) {
            inc(h[pos], h[pos + 1], -1);
         }
         
         h[pos] = val;
         
         if (pos) {
            inc(h[pos], h[pos - 1], 1);
         }
         if (pos + 1 < n) {
            inc(h[pos], h[pos + 1], 1);
         }
      } else {
         int H;
         cin >> H;
         cout << get(1, 1, N, H, H) << '\n';
      }
   }
   
   return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 12 ms 15104 KB Output is correct
3 Correct 12 ms 14700 KB Output is correct
4 Correct 13 ms 14956 KB Output is correct
5 Correct 12 ms 15084 KB Output is correct
6 Correct 14 ms 15232 KB Output is correct
7 Correct 8 ms 12780 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 12 ms 15104 KB Output is correct
3 Correct 12 ms 14700 KB Output is correct
4 Correct 13 ms 14956 KB Output is correct
5 Correct 12 ms 15084 KB Output is correct
6 Correct 14 ms 15232 KB Output is correct
7 Correct 8 ms 12780 KB Output is correct
8 Correct 86 ms 1004 KB Output is correct
9 Correct 237 ms 19288 KB Output is correct
10 Correct 238 ms 19584 KB Output is correct
11 Correct 77 ms 1644 KB Output is correct
12 Correct 137 ms 3308 KB Output is correct
13 Correct 148 ms 19308 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 12 ms 15104 KB Output is correct
3 Correct 12 ms 14700 KB Output is correct
4 Correct 13 ms 14956 KB Output is correct
5 Correct 12 ms 15084 KB Output is correct
6 Correct 14 ms 15232 KB Output is correct
7 Correct 8 ms 12780 KB Output is correct
8 Correct 86 ms 1004 KB Output is correct
9 Correct 237 ms 19288 KB Output is correct
10 Correct 238 ms 19584 KB Output is correct
11 Correct 77 ms 1644 KB Output is correct
12 Correct 137 ms 3308 KB Output is correct
13 Correct 148 ms 19308 KB Output is correct
14 Correct 470 ms 19436 KB Output is correct
15 Correct 479 ms 19564 KB Output is correct
16 Correct 468 ms 19436 KB Output is correct
17 Correct 467 ms 19436 KB Output is correct
18 Correct 484 ms 19564 KB Output is correct