Submission #337625

#	Time	Username	Problem	Language	Result	Execution time	Memory
337625		boykut	Simple game (IZhO17_game)	C++14	100 / 100	484 ms	19584 KiB

game

#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 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51