Submission #1034498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034498		pera	Simple game (IZhO17_game)	C++17	100 / 100	163 ms	6924 KiB

game

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1 , M = 1e6 + 1;
int n , q;
vector<int> h(N) , t(M);
void upd(int u , int x){
   while(u < M){
      t[u] += x;
      u += u&-u;
   }
}
int GET(int u){
   int sum = 0;
   while(u > 0){
      sum += t[u];
      u -= u&-u;
   }
   return sum;
}
int main(){
   cin >> n >> q;
   for(int i = 1;i <= n;i ++){
      cin >> h[i];
   }
   auto UPD = [&](int id , int x){
      if(h[id] < h[id + 1]){
         upd(h[id] + 1 , x);
         upd(h[id + 1] , -x);
      }else if(h[id] > h[id + 1]){
         upd(h[id + 1] + 1 , x);
         upd(h[id] , -x);
      }
   };
   for(int i = 1;i < n;i ++){
      UPD(i , 1);
   }
   while(q--){
      int type;
      cin >> type;
      if(type == 1){
         int pos , val;
         cin >> pos >> val;
         if(pos < n){
            UPD(pos , -1);
         }
         if(pos > 1){
            UPD(pos - 1 , -1);
         }
         h[pos] = val;
         if(pos < n){
            UPD(pos , 1);
         }
         if(pos > 1){
            UPD(pos - 1 , 1);
         }
      }else{
         int H;
         cin >> H;
         cout << GET(H) << endl;
      }
   }
}

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51