oj.uz

Submission #499388

# Submission time Handle Problem Language Result Execution time Memory
499388 2021-12-28T10:25:28 Z ismoilov Simple game (IZhO17_game) C++14
100 / 100
 55 ms 6852 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
#define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
#define fm(a,i,c) for(int (a) = (i); (a) > (c); (a)--)
#define fmm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
const int maxx = 1e6+6;
int tr[4*maxx];
int n, m;
void add(int x, int val){
	while(x < maxx){
		tr[x] += val;
		x += x & -x;
	}
}
void add(int l, int r, int val){
	if(l > r)
		swap(l, r);
	add(l, val);
	add(r+1, -val);
}
int get(int x){
	int s = 0;
	while(x > 0){
		s += tr[x];
		x -= x & -x;
	}
	return s;
}
int a[maxx];
void S()
{
	cin >> n >> m;
	fpp(i,1,n){
		cin >> a[i];
		if(i > 1)
			add(a[i-1], a[i], 1);
	}
	while(m--){
		int t;
		cin >> t;
		if(t == 1){
			int i, v;
			cin >> i >> v;
			if(i > 1)
				add(a[i-1], a[i], -1), add(a[i-1], v, 1);
			if(i < n)
				add(a[i], a[i+1], -1), add(v, a[i+1], 1);
			a[i] = v;
		}
		else{
			int i;
			cin >> i;
			cout << get(i) << "\n";
	// 		cout << get(i) - get(i-1) << "\n";
		}
	}
}
int main()
{
	IOS;
	S();
}

Compilation message

game.cpp: In function 'void S()':
game.cpp:7:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
      |                            ^
game.cpp:37:2: note: in expansion of macro 'fpp'
   37 |  fpp(i,1,n){
      |  ^~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 2 ms 3792 KB Output is correct
3 Correct 2 ms 3788 KB Output is correct
4 Correct 2 ms 3768 KB Output is correct
5 Correct 2 ms 3780 KB Output is correct
6 Correct 2 ms 3912 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 2 ms 3792 KB Output is correct
3 Correct 2 ms 3788 KB Output is correct
4 Correct 2 ms 3768 KB Output is correct
5 Correct 2 ms 3780 KB Output is correct
6 Correct 2 ms 3912 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 30 ms 1656 KB Output is correct
9 Correct 37 ms 6744 KB Output is correct
10 Correct 39 ms 6768 KB Output is correct
11 Correct 29 ms 1540 KB Output is correct
12 Correct 34 ms 2800 KB Output is correct
13 Correct 34 ms 2816 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 2 ms 3792 KB Output is correct
3 Correct 2 ms 3788 KB Output is correct
4 Correct 2 ms 3768 KB Output is correct
5 Correct 2 ms 3780 KB Output is correct
6 Correct 2 ms 3912 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 30 ms 1656 KB Output is correct
9 Correct 37 ms 6744 KB Output is correct
10 Correct 39 ms 6768 KB Output is correct
11 Correct 29 ms 1540 KB Output is correct
12 Correct 34 ms 2800 KB Output is correct
13 Correct 34 ms 2816 KB Output is correct
14 Correct 55 ms 6832 KB Output is correct
15 Correct 52 ms 6752 KB Output is correct
16 Correct 51 ms 6808 KB Output is correct
17 Correct 50 ms 6852 KB Output is correct
18 Correct 51 ms 6848 KB Output is correct