oj.uz

Submission #341382

# Submission time Handle Problem Language Result Execution time Memory
341382 2020-12-29T15:28:22 Z nandonathaniel Simple game (IZhO17_game) C++14
100 / 100
 360 ms 10860 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005,MAXV=1000005;

int bit[2][MAXV],a[MAXN];

void update(int now,int val,int id){
	for(int i=now;i<MAXV;i+=(i&(-i)))bit[id][i]+=val;
}

int query(int now,int id){
	int ret=0;
	for(int i=now;i>0;i-=(i&(-i)))ret+=bit[id][i];
	return ret;
}

int main(){
//	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,q,op,x,y;
	cin >> n >> q;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	if(n<=2){
		while(q--){
			cin >> op >> x;
			if(op==1){
				cin >> y;
				a[x]=y;
			}
			else{
				if(n==1)cout << 0 << '\n';
				else{
					if((a[1]>=x && a[2]<=x) || (a[2]>=x && a[1]<=x))cout << 1 << '\n';
					else cout << 0 << '\n';
				}
			}
		}
		return 0;
	}
	for(int i=1;i<n;i++){
		int j=i+1;
		update(min(a[i],a[j]),1,0);
		update(max(a[i],a[j]),1,1);
	}
	while(q--){
		cin >> op >> x;
		if(op==1){
			cin >> y;
			int j=x-1,k=x+1;
			bool skipj=false,skipk=false;
			if(j==0)skipj=true;
			if(k==n+1)skipk=true;
			if(!skipj){
				update(min(a[x],a[j]),-1,0);
				update(max(a[x],a[j]),-1,1);
			}
			if(!skipk){
				update(min(a[x],a[k]),-1,0);
				update(max(a[x],a[k]),-1,1);
			}
			a[x]=y;
			if(!skipj){
				update(min(a[x],a[j]),1,0);
				update(max(a[x],a[j]),1,1);
			}
			if(!skipk){
				update(min(a[x],a[k]),1,0);
				update(max(a[x],a[k]),1,1);
			}
		}
		else{
			int ans=n-1;
			ans-=query(x-1,1);
//			cout << "werner " << ans << '\n';
			ans-=(query(MAXV-1,0)-query(x,0));
			cout << ans << '\n';
		}
//		cout << "min" << endl;
//		for(int i=1;i<=5;i++){
//			cout << query(i,0)-query(i-1,0) << " ";
//		}
//		cout << endl;
//		cout << "max" << endl;
//		for(int i=1;i<=5;i++){
//			cout << query(i,1)-query(i-1,1) << " ";
//		}
//		cout << endl;
	}
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 8 ms 7020 KB Output is correct
3 Correct 7 ms 7020 KB Output is correct
4 Correct 8 ms 7040 KB Output is correct
5 Correct 7 ms 6892 KB Output is correct
6 Correct 7 ms 7020 KB Output is correct
7 Correct 5 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 8 ms 7020 KB Output is correct
3 Correct 7 ms 7020 KB Output is correct
4 Correct 8 ms 7040 KB Output is correct
5 Correct 7 ms 6892 KB Output is correct
6 Correct 7 ms 7020 KB Output is correct
7 Correct 5 ms 364 KB Output is correct
8 Correct 295 ms 1804 KB Output is correct
9 Correct 360 ms 10732 KB Output is correct
10 Correct 360 ms 10732 KB Output is correct
11 Correct 286 ms 1704 KB Output is correct
12 Correct 319 ms 3052 KB Output is correct
13 Correct 326 ms 2924 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 8 ms 7020 KB Output is correct
3 Correct 7 ms 7020 KB Output is correct
4 Correct 8 ms 7040 KB Output is correct
5 Correct 7 ms 6892 KB Output is correct
6 Correct 7 ms 7020 KB Output is correct
7 Correct 5 ms 364 KB Output is correct
8 Correct 295 ms 1804 KB Output is correct
9 Correct 360 ms 10732 KB Output is correct
10 Correct 360 ms 10732 KB Output is correct
11 Correct 286 ms 1704 KB Output is correct
12 Correct 319 ms 3052 KB Output is correct
13 Correct 326 ms 2924 KB Output is correct
14 Correct 279 ms 10732 KB Output is correct
15 Correct 287 ms 10860 KB Output is correct
16 Correct 282 ms 10796 KB Output is correct
17 Correct 279 ms 10860 KB Output is correct
18 Correct 286 ms 10732 KB Output is correct