oj.uz

Submission #1094239

# Submission time Handle Problem Language Result Execution time Memory
1094239 2024-09-29T06:38:56 Z Sunbae Simple game (IZhO17_game) C++17
100 / 100
 46 ms 6916 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 1e6 + 5;
int a[N], bit[M];
void upd(int i, int v){ for(; i<M; i+=i&-i) bit[i] += v;}
int qry(int i){ int r = 0; for(; i; i-=i&-i) r += bit[i]; return r;}
signed main(){
	int n, q; scanf("%d %d", &n, &q);
	for(int i = 0; i<n; ++i) scanf("%d", a+i);
	for(int i = 1; i<n; ++i){
		int l = a[i], r = a[i-1]; if(l > r) swap(l, r); ++l; --r;
		if(l <= r) upd(l, +1), upd(r+1, -1);
	}
	while(q--){
		int t, i, v, l, r, h; scanf("%d", &t);
		if(t == 1){
			scanf("%d %d", &i, &v); --i;
			for(int j = 0; j<2; ++j){
				if(!j && !i) continue;
				if(j && i == n-1) continue;
				l = a[i]; r = ((!j) ? a[i-1] : a[i+1]); if(l > r) swap(l, r); ++l; --r;
				if(l <= r) upd(l, -1), upd(r+1, +1);
				l = v; r = ((!j) ? a[i-1] : a[i+1]); if(l > r) swap(l, r); ++l; --r;
				if(l <= r) upd(l, +1), upd(r+1, -1);
			}
			a[i] = v;
		}else{
			scanf("%d", &h); printf("%d\n", qry(h));
		}
	}
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:8:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |  int n, q; scanf("%d %d", &n, &q);
      |            ~~~~~^~~~~~~~~~~~~~~~~
game.cpp:9:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  for(int i = 0; i<n; ++i) scanf("%d", a+i);
      |                           ~~~~~^~~~~~~~~~~
game.cpp:15:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   int t, i, v, l, r, h; scanf("%d", &t);
      |                         ~~~~~^~~~~~~~~~
game.cpp:17:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |    scanf("%d %d", &i, &v); --i;
      |    ~~~~~^~~~~~~~~~~~~~~~~
game.cpp:28:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |    scanf("%d", &h); printf("%d\n", qry(h));
      |    ~~~~~^~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 3 ms 4188 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 3 ms 4188 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 29 ms 1800 KB Output is correct
9 Correct 36 ms 6740 KB Output is correct
10 Correct 38 ms 6740 KB Output is correct
11 Correct 20 ms 1628 KB Output is correct
12 Correct 32 ms 2896 KB Output is correct
13 Correct 30 ms 2692 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 3 ms 4188 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 29 ms 1800 KB Output is correct
9 Correct 36 ms 6740 KB Output is correct
10 Correct 38 ms 6740 KB Output is correct
11 Correct 20 ms 1628 KB Output is correct
12 Correct 32 ms 2896 KB Output is correct
13 Correct 30 ms 2692 KB Output is correct
14 Correct 46 ms 6916 KB Output is correct
15 Correct 46 ms 6912 KB Output is correct
16 Correct 45 ms 6736 KB Output is correct
17 Correct 43 ms 6740 KB Output is correct
18 Correct 45 ms 6736 KB Output is correct