Submission #291389

#	Time	Username	Problem	Language	Result	Execution time	Memory
291389		kshitij_sodani	Simple game (IZhO17_game)	C++14	100 / 100	71 ms	6904 KiB

game

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
//#define endl '\n'
int n,m;
int it[100001];
int tree[1000001];
void u(int i,int j){
	while(i<1000001){
		tree[i]+=j;
		i+=(i&-i);
	}
}
int ss(int i){
	int su=0;
	while(i>0){
		su+=tree[i];
		i-=(i&-i);
	}
	return su;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>it[i];
	}
	for(int i=0;i<n-1;i++){
		int aa=min(it[i],it[i+1]);
		int bb=max(it[i],it[i+1]);
		u(aa,1);
		u(bb,-1);
	}

	for(int ii=0;ii<m;ii++){
		int tt;
		cin>>tt;
		if(tt==1){
			int i,val;
			cin>>i>>val;
			i--;
			if(i>0){
				int aa=min(it[i],it[i-1]);
				int bb=max(it[i],it[i-1]);
				u(aa,-1);
				u(bb,1);
			}
			if(i<n-1){
				int aa=min(it[i],it[i+1]);
				int bb=max(it[i],it[i+1]);
				u(aa,-1);
				u(bb,1);
			}
			it[i]=val;

			if(i>0){
				int aa=min(it[i],it[i-1]);
				int bb=max(it[i],it[i-1]);
				u(aa,1);
				u(bb,-1);
			}
			if(i<n-1){
				int aa=min(it[i],it[i+1]);
				int bb=max(it[i],it[i+1]);
				u(aa,1);
				u(bb,-1);
			}
		}
		else{
			int aa;
			cin>>aa;
			cout<<ss(aa)<<'\n';
		}
	}
	//








	return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51