Submission #494947

#	Time	Username	Problem	Language	Result	Execution time	Memory
494947		luka1234	Simple game (IZhO17_game)	C++14	100 / 100	227 ms	9128 KiB

game

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;
int f1[1000002];
int f2[1000002];
int n,m;
int nmax=1000001;
int h[100001];
int getsum1(int v){
    int ans=0;
    for(int i=v;i>=1;i=(i&(i-1))){
        ans+=f1[i];
    }
    return ans;
}
int getsum2(int v){
    int ans=0;
    for(int i=v;i>=1;i=(i&(i-1))){
        ans+=f2[i];
    }
    return ans;
}
void update1(int v,int x){
    for(int i=v;i<=nmax;i=2*i-(i&(i-1))){
        f1[i]+=x;
    }
}
void update2(int v,int x){
    for(int i=v;i<=nmax;i=2*i-(i&(i-1))){
        f2[i]+=x;
    }
}
int rangesum(int l,int r){
    int sum1=getsum1(r)+getsum2(r)*r;
    int sum2=getsum1(l-1)+getsum2(l-1)*(l-1);
    return(sum1-sum2);
}
void rangeupdate(int l,int r,int x){
	int u1=-(l-1)*x;
    int u2=r*x;
    update1(l,u1);
    update1(r+1,u2);
    update2(l,x);
    update2(r+1,-x);
}
int main(){
	cin>>n>>m;
	for(int k=1;k<=n;k++){
		cin>>h[k];
	}
	for(int k=2;k<=n;k++){
		int l=min(h[k],h[k-1]);
		int r=max(h[k],h[k-1]);
		rangeupdate(l,r,1);
	}
	while(m--){
		int ind;
		cin>>ind;
		if(ind==1){
			int pos,val;
			cin>>pos>>val;
			if(pos>1&&pos<n){
				int l1=min(h[pos],h[pos-1]);
				int r1=max(h[pos],h[pos-1]);
				int l2=min(h[pos],h[pos+1]);
				int r2=max(h[pos],h[pos+1]);
				h[pos]=val;
				int l3=min(h[pos],h[pos-1]);
				int r3=max(h[pos],h[pos-1]);
				int l4=min(h[pos],h[pos+1]);
				int r4=max(h[pos],h[pos+1]);
				rangeupdate(l1,r1,-1);
				rangeupdate(l2,r2,-1);
				rangeupdate(l3,r3,1);
				rangeupdate(l4,r4,1);
			}
			else{
				if(pos==1){
					int l2=min(h[pos],h[pos+1]);
				    int r2=max(h[pos],h[pos+1]);
				    h[pos]=val;
				    int l4=min(h[pos],h[pos+1]);
				    int r4=max(h[pos],h[pos+1]);
				    rangeupdate(l2,r2,-1);
				    rangeupdate(l4,r4,1);
				}
				else{
					int l1=min(h[pos],h[pos-1]);
				    int r1=max(h[pos],h[pos-1]);
				    h[pos]=val;
				    int l3=min(h[pos],h[pos-1]);
				    int r3=max(h[pos],h[pos-1]);
				    rangeupdate(l1,r1,-1);
				    rangeupdate(l3,r3,1);
				}
			}
		}
		else{
			int y;
			cin>>y;
			int ans=rangesum(y,y);
			cout<<ans<<"\n";
		}
	}
    return 0;
}

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