oj.uz

Submission #63361

# Submission time Handle Problem Language Result Execution time Memory
63361 2018-08-01T14:50:38 Z Tenuun Simple game (IZhO17_game) C++17
100 / 100
 288 ms 22708 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
int tr[1000001];
 
void update(int ind, int val){
	while(ind<=1000001){
		tr[ind]+=val;
		ind+=ind&-ind;
	}
}
 
int get(int ind){
	int ans=0;
	while(ind){
		ans+=tr[ind];
		ind-=ind&-ind;
	}
	return ans;
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	memset(tr, 0, sizeof tr);
	int n, m, pos, val, t;
	cin >> n >> m;
	int a[n+1];
	for(int i=1; i<=n; i++){
		cin >> a[i];
		if(i>1){
			update(min(a[i], a[i-1]), 1);
			update(max(a[i], a[i-1])+1, -1);
		}
	}
	while(m--){
		cin >> t;
		if(t==1){
			cin >> pos >> val;
			if(pos>1){
				update(min(a[pos], a[pos-1]), -1);
				update(max(a[pos], a[pos-1])+1, 1);
			}
			if(pos+1<=n){
				update(min(a[pos], a[pos+1]), -1);
				update(max(a[pos], a[pos+1])+1, 1);
			}
			a[pos]=val;
			if(pos>1){
				update(min(a[pos], a[pos-1]), 1);
				update(max(a[pos], a[pos-1])+1, -1);
			}
			if(pos+1<=n){
				update(min(a[pos], a[pos+1]), 1);
				update(max(a[pos], a[pos+1])+1, -1);
			}
		}
		else{
			cin >> val;
			cout << get(val) << endl;
		}
	}
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4216 KB Output is correct
2 Correct 8 ms 4328 KB Output is correct
3 Correct 7 ms 4532 KB Output is correct
4 Correct 9 ms 4532 KB Output is correct
5 Correct 9 ms 4620 KB Output is correct
6 Correct 10 ms 4620 KB Output is correct
7 Correct 9 ms 4620 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4216 KB Output is correct
2 Correct 8 ms 4328 KB Output is correct
3 Correct 7 ms 4532 KB Output is correct
4 Correct 9 ms 4532 KB Output is correct
5 Correct 9 ms 4620 KB Output is correct
6 Correct 10 ms 4620 KB Output is correct
7 Correct 9 ms 4620 KB Output is correct
8 Correct 197 ms 5960 KB Output is correct
9 Correct 278 ms 8036 KB Output is correct
10 Correct 280 ms 9868 KB Output is correct
11 Correct 237 ms 10000 KB Output is correct
12 Correct 245 ms 11788 KB Output is correct
13 Correct 288 ms 13284 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4216 KB Output is correct
2 Correct 8 ms 4328 KB Output is correct
3 Correct 7 ms 4532 KB Output is correct
4 Correct 9 ms 4532 KB Output is correct
5 Correct 9 ms 4620 KB Output is correct
6 Correct 10 ms 4620 KB Output is correct
7 Correct 9 ms 4620 KB Output is correct
8 Correct 197 ms 5960 KB Output is correct
9 Correct 278 ms 8036 KB Output is correct
10 Correct 280 ms 9868 KB Output is correct
11 Correct 237 ms 10000 KB Output is correct
12 Correct 245 ms 11788 KB Output is correct
13 Correct 288 ms 13284 KB Output is correct
14 Correct 209 ms 14928 KB Output is correct
15 Correct 225 ms 17044 KB Output is correct
16 Correct 182 ms 18840 KB Output is correct
17 Correct 186 ms 20668 KB Output is correct
18 Correct 236 ms 22708 KB Output is correct