Submission #83587

#	Time	Username	Problem	Language	Result	Execution time	Memory
83587		ToadDaveski	Simple game (IZhO17_game)	C++14	0 / 100	254 ms	263168 KiB

game

#include <bits/stdc++.h>
#define ll int
using namespace std;
ll t[4000001],a[100001];
void update(ll v,ll l,ll r,ll tl,ll tr,ll val)
{
    //cout<<"/"<<tl<<" "<<tr<<endl;
    if (tl>tr) return;
    if (l>r) return;
    if (l==tl && r==tr){
        t[v]+=val;
        return;
    }
    ll bm=(l+r)/2;
    update(v*2,l,bm,tl,min(tr,bm),val);
    update(v*2+1,bm+1,r,max(tl,bm+1),tr,val);
}
ll findans(ll v,ll l,ll r,ll tl)
{
    //cout<<l<<" "<<r<<endl;
    if (tl==l && tl==r)
        return t[v];
    ll bm=(l+r)/2;
    if (tl>bm)
        return t[v]+findans(v*2+1,bm+1,r,tl);
    return t[v]+findans(v*2,l,bm,tl);
}
void update1(ll v,ll l,ll r,ll tl,ll tr,ll val)
{
    if (tl>tr) swap(tl,tr);
    update(v,l,r,tl,tr,val);
}
int main()
{
    //freopen("game.in","r",stdin);
    //freopen("game.out","w",stdout);
    ll n=1e6+1,nn,m,i,j;
    cin>>nn>>m;
    for(i=1;i<=nn;i++)
        cin>>a[i],n=max(a[i],n);
    //cout<<n<<endl;
    for(i=1;i<nn;i++)
    {
        ll x=a[i],y=a[i+1];
        if (x>y) swap(x,y);
        update(1,1,n,x,y,1);
    }
    //for(i=1;i<=4*nn;i++)
      //  cout<<t[i]<<" ";
    //cout<<endl;
    for(ll it=1;it<=m;it++)
    {
        ll ch;
        cin>>ch;
        if (ch==1)
        {
            ll x,y;
            cin>>x>>y;
            n=max(n,y);
            if (x!=1) update1(1,1,n,a[x],a[x-1],-1),update1(1,1,n,y,a[x-1],1);
            if (x!=n) update1(1,1,n,a[x],a[x+1],-1),update1(1,1,n,y,a[x+1],1);
            a[x]=y;
        }
        else
        {
            ll x;
            cin>>x;
            cout<<findans(1,1,n,x)<<endl;
        }
    }
}

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:37:23: warning: unused variable 'j' [-Wunused-variable]
     ll n=1e6+1,nn,m,i,j;
                       ^

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