Submission #344448

#	Time	Username	Problem	Language	Result	Execution time	Memory
344448		fixikmila	Simple game (IZhO17_game)	C++14	100 / 100	356 ms	19052 KiB

game

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll>pll;
typedef long double ld;
ll bin_pow(ll a,ll b){
    if(b==0)return 1;
    if(b%2==0){
        ll t=bin_pow(a,b/2);
        return t*t%MOD;
    }
    else return a*bin_pow(a,b-1)%MOD;
}
ll sum[4000005];
void update(int idx,int val,int v,int tl,int tr){
if(idx==tl&&tl==tr){
    sum[v]+=val;
    return;
}
if(tl>idx||tr<idx)return;
int tm=(tl+tr)/2;
update(idx,val,2*v,tl,tm),update(idx,val,2*v+1,tm+1,tr);
sum[v]=sum[2*v]+sum[2*v+1];
}
ll sum1(int idx,int v,int tl,int tr){
    if(tl>=0&&tr<=idx)return sum[v];
    if(tl>idx||tr<0)return 0;
    int tm=(tl+tr)/2;
    return sum1(idx,2*v,tl,tm)+sum1(idx,2*v+1,tm+1,tr);
}
int main()
{
    //freopen("stones.in","r",stdin);
    //freopen("stones.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
    cin>>n>>m;
    vector<ll>a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=1;i<n;i++){
        l=a[i-1],r=a[i];
        if(l>r)swap(l,r);
        if(l==r)continue;
        update(l+1,1,1,0,1e6);
        update(r,-1,1,0,1e6);
    }
    while(m--){
        cin>>z;
        if(z==1){
                cin>>x>>y;
        x--;
        //update(a[x],-1,1,0,n-1);
        //update(a[x]+1,1,1,0,n-1);
        if(x){
            l=a[x-1],r=a[x];
            if(l>r)swap(l,r);
        update(l+1,-1,1,0,1e6);
        update(r,1,1,0,1e6);
        }
        if(x<n-1){
            l=a[x+1],r=a[x];
            if(l>r)swap(l,r);
        update(l+1,-1,1,0,1e6);
        update(r,1,1,0,1e6);
            }
        a[x]=y;
        if(x){
            l=a[x-1],r=a[x];
            if(l>r)swap(l,r);
        update(l+1,1,1,0,1e6);
        update(r,-1,1,0,1e6);
        }
        if(x<n-1){
            l=a[x+1],r=a[x];
            if(l>r)swap(l,r);
        update(l+1,1,1,0,1e6);
        update(r,-1,1,0,1e6);
            }
        //    update(a[x],1,1,0,n-1);
       // update(a[x]+1,-1,1,0,n-1);
        }
        else{
            cin>>x;
            ans=sum1(x,1,0,1e6);
            cout<<ans;
            cout<<"\n";
        }
    }
    return 0;
}

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:38:8: warning: unused variable 't' [-Wunused-variable]
   38 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |        ^
game.cpp:38:16: warning: unused variable 'k' [-Wunused-variable]
   38 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                ^
game.cpp:38:20: warning: unused variable 'sum' [-Wunused-variable]
   38 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                    ^~~
game.cpp:38:52: warning: unused variable 'mn' [-Wunused-variable]
   38 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                                    ^~
game.cpp:38:65: warning: unused variable 'mx' [-Wunused-variable]
   38 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                                                 ^~

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