oj.uz

Submission #97666

# Submission time Handle Problem Language Result Execution time Memory
97666 2019-02-17T17:16:57 Z Kalam Simple game (IZhO17_game) C++11
100 / 100
 132 ms 6968 KB 
// KALAM
# include<bits/stdc++.h>

using namespace std;

const int N = 1000000 + 77;
int n , q;
int a[N] , Fen[N];
inline void Add(int x , int y){
   for(;x < N;x += x & - x)
      Fen[x] += y;
}
inline int Get(int x){
   int res = 0;
   for(;x;x -= x & - x)
      res += Fen[x];
   return res;
}
int main() {
   scanf("%d %d" , & n , & q);
   for(int i = 1;i <= n;++ i) {
      scanf("%d" , a + i);
      if(i > 1)
         Add(max(a[i] , a[i - 1]) , - 1) , Add(min(a[i] , a[i - 1]) , 1);
   }
   while(q --){
      int tp , x , y;
      scanf("%d %d" , & tp , & x);
      if(tp == 2){
         printf("%d\n" , Get(x));
         continue ;
      }
      scanf("%d" , & y);
      if(x > 1) {
         Add(max(a[x] , a[x - 1]) , 1) , Add(min(a[x] , a[x - 1]) , - 1);
         Add(max(y , a[x - 1]) , - 1) , Add(min(y , a[x - 1]) , 1);
      }
      if(x < n) {
         Add(max(a[x] , a[x + 1]) , 1) , Add(min(a[x] , a[x + 1]) , - 1);
         Add(max(y , a[x + 1]) , - 1) , Add(min(y , a[x + 1]) , 1);
      }
      a[x] = y;
   }

   return 0;
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:20:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d" , & n , & q);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~
game.cpp:22:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d" , a + i);
       ~~~~~^~~~~~~~~~~~~~
game.cpp:28:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d" , & tp , & x);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~
game.cpp:33:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d" , & y);
       ~~~~~^~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 6 ms 3968 KB Output is correct
3 Correct 6 ms 3968 KB Output is correct
4 Correct 8 ms 3968 KB Output is correct
5 Correct 6 ms 3840 KB Output is correct
6 Correct 6 ms 3968 KB Output is correct
7 Correct 2 ms 420 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 6 ms 3968 KB Output is correct
3 Correct 6 ms 3968 KB Output is correct
4 Correct 8 ms 3968 KB Output is correct
5 Correct 6 ms 3840 KB Output is correct
6 Correct 6 ms 3968 KB Output is correct
7 Correct 2 ms 420 KB Output is correct
8 Correct 51 ms 1744 KB Output is correct
9 Correct 92 ms 6884 KB Output is correct
10 Correct 93 ms 6904 KB Output is correct
11 Correct 74 ms 1656 KB Output is correct
12 Correct 76 ms 2812 KB Output is correct
13 Correct 62 ms 2792 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 6 ms 3968 KB Output is correct
3 Correct 6 ms 3968 KB Output is correct
4 Correct 8 ms 3968 KB Output is correct
5 Correct 6 ms 3840 KB Output is correct
6 Correct 6 ms 3968 KB Output is correct
7 Correct 2 ms 420 KB Output is correct
8 Correct 51 ms 1744 KB Output is correct
9 Correct 92 ms 6884 KB Output is correct
10 Correct 93 ms 6904 KB Output is correct
11 Correct 74 ms 1656 KB Output is correct
12 Correct 76 ms 2812 KB Output is correct
13 Correct 62 ms 2792 KB Output is correct
14 Correct 130 ms 6892 KB Output is correct
15 Correct 131 ms 6904 KB Output is correct
16 Correct 132 ms 6968 KB Output is correct
17 Correct 108 ms 6904 KB Output is correct
18 Correct 119 ms 6884 KB Output is correct