Submission #341382

#	Time	Username	Problem	Language	Result	Execution time	Memory
341382		nandonathaniel	Simple game (IZhO17_game)	C++14	100 / 100	360 ms	10860 KiB

game

#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 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51