Submission #888431

#	Time	Username	Problem	Language	Result	Execution time	Memory
888431		pcc	Simple game (IZhO17_game)	C++14	100 / 100	49 ms	9000 KiB

game

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 1e6+10;
int n,q;
int arr[mxn];
int bit[mxn];

void modify(int p,int v){
	for(;p<mxn;p+=p&-p)bit[p] += v;
	return;
}
int getval(int p){
	int re = 0;
	for(;p>0;p-= p&-p)re += bit[p];
	return re;
}

void add(int l,int r){
	if(r<l)swap(l,r);
	modify(l,1);
	modify(r+1,-1);
}
void del(int l,int r){
	if(r<l)swap(l,r);
	modify(l,-1);
	modify(r+1,1);
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i = 1;i<=n;i++)cin>>arr[i];
	for(int i = 2;i<=n;i++){
		add(arr[i-1],arr[i]);
	}
	while(q--){
		int t;
		cin>>t;
		if(t == 1){
			int p,v;
			cin>>p>>v;
			if(p != 1)del(arr[p-1],arr[p]);
			if(p != n)del(arr[p],arr[p+1]);
			arr[p] = v;
			if(p != n)add(arr[p],arr[p+1]);
			if(p != 1)add(arr[p],arr[p-1]);
		}
		else{
			int p;
			cin>>p;
			cout<<getval(p)<<'\n';
		}
	}
	return 0;
}

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