oj.uz

답안 #1034498

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1034498 2024-07-25T14:29:47 Z pera Simple game (IZhO17_game) C++17
100 / 100
 163 ms 6924 KB 
#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.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4756 KB Output is correct
2 Correct 4 ms 4696 KB Output is correct
3 Correct 4 ms 4700 KB Output is correct
4 Correct 3 ms 4700 KB Output is correct
5 Correct 3 ms 4576 KB Output is correct
6 Correct 3 ms 4700 KB Output is correct
7 Correct 3 ms 4700 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4756 KB Output is correct
2 Correct 4 ms 4696 KB Output is correct
3 Correct 4 ms 4700 KB Output is correct
4 Correct 3 ms 4700 KB Output is correct
5 Correct 3 ms 4576 KB Output is correct
6 Correct 3 ms 4700 KB Output is correct
7 Correct 3 ms 4700 KB Output is correct
8 Correct 148 ms 5712 KB Output is correct
9 Correct 140 ms 6840 KB Output is correct
10 Correct 139 ms 6864 KB Output is correct
11 Correct 128 ms 5528 KB Output is correct
12 Correct 163 ms 6480 KB Output is correct
13 Correct 139 ms 6740 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4756 KB Output is correct
2 Correct 4 ms 4696 KB Output is correct
3 Correct 4 ms 4700 KB Output is correct
4 Correct 3 ms 4700 KB Output is correct
5 Correct 3 ms 4576 KB Output is correct
6 Correct 3 ms 4700 KB Output is correct
7 Correct 3 ms 4700 KB Output is correct
8 Correct 148 ms 5712 KB Output is correct
9 Correct 140 ms 6840 KB Output is correct
10 Correct 139 ms 6864 KB Output is correct
11 Correct 128 ms 5528 KB Output is correct
12 Correct 163 ms 6480 KB Output is correct
13 Correct 139 ms 6740 KB Output is correct
14 Correct 120 ms 6924 KB Output is correct
15 Correct 116 ms 6908 KB Output is correct
16 Correct 107 ms 6736 KB Output is correct
17 Correct 120 ms 6704 KB Output is correct
18 Correct 115 ms 6704 KB Output is correct