Submission #1128538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128538		the_ZHER	Simple game (IZhO17_game)	C++20	100 / 100	200 ms	57024 KiB

game

#include <bits/stdc++.h>
#define int long long
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 1e6+5;
const int inf = 1e9;
const int mod=1e9+7;
struct edge{
    int pos,val,t;
};
vector<int>v;
vector<edge>v1;
int dp[N];
int t[4*N];
int add[4*N];
void build(int n,int tl,int tr){
    if(tl==tr){
        t[n]=dp[tl];
        return ;
    }
    int mid=(tl+tr)/2;
    build(n*2,tl,mid);
    build(n*2+1,mid+1,tr);
    t[n]=t[n*2]+t[n*2+1];
}
void push(int n,int tl,int tr){
    if(add[n]!=0){
        t[n]+=(tr-tl+1)*add[n];
        add[n*2]+=add[n];
        add[n*2+1]+=add[n];
        add[n]=0;
    }
}
void upd(int n,int tl,int tr,int l,int r,int x){
    push(n,tl,tr);
    if(tr<l||r<tl){
        return ;
    }
    if(l<=tl&&tr<=r){
        add[n]+=x;
        push(n,tl,tr);
        return ;
    }
    int mid=(tl+tr)/2;
    upd(n*2,tl,mid,l,r,x);
    upd(n*2+1,mid+1,tr,l,r,x);
}
int get(int n,int tl,int tr,int pos){
    push(n,tl,tr);
    if(tl==tr){
        return t[n];
    }
    int mid=(tl+tr)/2;
    if(pos<=mid){
        return get(n*2,tl,mid,pos);
    }else{
        return get(n*2+1,mid+1,tr,pos);
    }
}
signed main(){
//freopen("game.in", "r", stdin);
//freopen("game.out", "w", stdout);
    boost 
    int n,m;
    cin>>n>>m;
    v.push_back(0);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        v.push_back(x);
    }
    for(int i=1;i<n;i++){
        int l=min(v[i],v[i+1]);
        int r=max(v[i],v[i+1]);
        dp[l]++;
        dp[r+1]--;
    }
    for(int i=1;i<=N-5;i++){
        dp[i]+=dp[i-1];
    }
    build(1,1,N-5);
    for(int i=1;i<=m;i++){
        int t;
        cin>>t;
        if(t==1){
            int pos,val;
            cin>>pos>>val;
            if(pos!=n){
                int l=min(v[pos],v[pos+1]);
                int r=max(v[pos],v[pos+1]);
                upd(1,1,N-5,l,r,-1);
            }
            if(pos!=1){
                int l=min(v[pos],v[pos-1]);
                int r=max(v[pos],v[pos-1]);
                upd(1,1,N-5,l,r,-1);                
            }
            v[pos]=val;
           if(pos!=n){
                int l=min(v[pos],v[pos+1]);
                int r=max(v[pos],v[pos+1]);
                upd(1,1,N-5,l,r,1);
            }
            if(pos!=1){
                int l=min(v[pos],v[pos-1]);
                int r=max(v[pos],v[pos-1]);
                upd(1,1,N-5,l,r,1);                
            }
        }else{
            int x;
            cin>>x;
            cout<<get(1,1,N-5,x)<<"\n";
        }
    }
}

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