Submission #1130310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130310		brover29	Simple game (IZhO17_game)	C++20	100 / 100	266 ms	34644 KiB

game

#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = long long;
const ll N=1e6+29;
const string br="617283";
#define sz(a)(ll)a.size()
#define f first
#define s second

ll n,m,st[4*N],h[N],z[4*N];
void push(ll v,ll l,ll r){
    if(!z[v])return;
    ll mid=(r+l)>>1;
    z[v*2]+=z[v];
    z[v*2+1]+=z[v];
    st[v*2]+=z[v]*(mid-l+1);
    st[v*2+1]+=z[v]*(r-mid);
    z[v]=0;
}
void update(ll v,ll l,ll r,ll x,ll y,ll value){
    if(l>y||x>r)return;
    if(x<=l&&r<=y){
        st[v]+=(r-l+1)*value;
        z[v]+=value;
        return;
    }
    push(v,l,r);
    ll mid=(r+l)>>1;
    update(v*2,l,mid,x,y,value);
    update(v*2+1,mid+1,r,x,y,value);
    st[v]=st[v*2]+st[v*2+1];
}
ll get(ll v,ll l,ll r,ll x,ll y){
    if(l>y||x>r)return 0;
    if(x<=l&&r<=y){
        return st[v];
    }
    push(v,l,r);
    ll mid=(r+l)>>1;

    return get(v*2,l,mid,x,y)+get(v*2+1,mid+1,r,x,y);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  

    cin>>n>>m;

    for(ll i=1;i<=n;i++){
        cin>>h[i];
        if(i>1)update(1,1,N-29,min(h[i],h[i-1]),max(h[i],h[i-1]),1);//cout<<get(1,1,N-29,3,3)<<'\n';
    }while(m--){
        ll t;
        cin>>t;
        if(t==1){
           ll i,val;
           cin>>i>>val;
           if(i<n)update(1,1,N-29,min(h[i],h[i+1]),max(h[i],h[i+1]),-1);
           if(i>1)update(1,1,N-29,min(h[i],h[i-1]),max(h[i],h[i-1]),-1);
           h[i]=val;
           if(i<n)update(1,1,N-29,min(h[i],h[i+1]),max(h[i],h[i+1]),1);
           if(i>1)update(1,1,N-29,min(h[i],h[i-1]),max(h[i],h[i-1]),1);
        }else{
            ll h;
            cin>>h;
            cout<<get(1,1,N-29,h,h)<<'\n';
        }
    }
}

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