Submission #522915

#	Time	Username	Problem	Language	Result	Execution time	Memory
522915		dostigator	Simple game (IZhO17_game)	C++17	0 / 100	12 ms	11136 KiB

game

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;
#define IShowSpeed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define popcnt __builtin_popcount
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define mii map<int,int>
#define pll pair<ll,ll>
#define mll map<ll,ll>
#define pb push_back
#define vt vector
#define endl '\n'
#define X first
#define Y second
typedef long double ld;
typedef long long ll;
const ll dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},N=1e6+10;
const ll mod=1e9+7,inf=1e18;
int n,q,y[N],t[4*N];
void upd(int l,int r,int val,int v=0,int tl=0,int tr=N-1) {
	if(tl>=l && tr<=r){
		t[v]+=val;
		return;
	}
	if(tl+1>r || l+1>tr)return;
	int mid=(tl+tr)>>1;
	upd(l,r,val,v+v+1,tl,mid);
	upd(l,r,val,v+v+2,mid,tr);
}
int get(int id,int res,int v=0,int tl=0,int tr=N-1) {
	res+=t[v];
	if(tr-tl==1)return res;
	int mid=(tl+tr)>>1;
	if(id<=mid) return get(id,res,v*2+1,tl,mid);
	else return get(id,res,v*2+2,mid+1,tr);
}
void solve(){
    cin>>n>>q;
	for(int i=1; i<=n; ++i) cin>>y[i];
	for(int i=1; i<n; ++i) {
		int l=min(y[i],y[i+1]),r=max(y[i],y[i+1]);
		upd(l-1,r,1);
	}
	while(q--){
		int tp;
		cin>>tp;
		int i,d;
		if(tp==1) {
			cin>>i>>d;
			if(i<n){
				int l=min(y[i],y[i+1]),r=max(y[i],y[i+1]);
				upd(l-1,r,-1);
			}
			if(i>1) {
				int l=min(y[i],y[i-1]),r=max(y[i],y[i-1]);
				upd(l-1,r,-1);
			}
			y[i]=d;
			if(i<n){
				int l=min(y[i],y[i+1]),r=max(y[i],y[i+1]);
				upd(l-1,r,1);
			}
			if(i>1){
				int l=min(y[i],y[i-1]),r=max(y[i],y[i-1]);
				upd(l-1,r,1);
			}
		}
		else{
			cin>>d;
			cout<<get(d,0)<<endl;
		}
	}
}
int main() {
    IShowSpeed;
    int tt=1;
    //cin>>tt;
    while(tt--) solve();
}

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