Submission #63361

#	Time	Username	Problem	Language	Result	Execution time	Memory
63361		Tenuun	Simple game (IZhO17_game)	C++17	100 / 100	288 ms	22708 KiB

game

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