Submission #83594

#	Time	Username	Problem	Language	Result	Execution time	Memory
83594		ToadDaveski	Simple game (IZhO17_game)	C++14	100 / 100	472 ms	35560 KiB

game

#include <bits/stdc++.h>
#define ll long long
#define INF 1000000
using namespace std;
ll t[8000001];
ll a[100001];
void update(ll x,ll l,ll r,ll tl,ll tr,ll value)
{
    //cout<<l<<" "<<r<<" "<<tl<<" "<<tr<<endl;
    if (tl>tr)
        return;
    if (tl==l && tr==r)
    {
        t[x]+=value;
        //cout<<l<<" "<<r<<" "<<t[x]<<endl;
        return ;
    }
    else
    {
        ll bm=(l+r)/2;
        update(x*2,l,bm,tl,min(tr,bm),value);
        update(x*2+1,bm+1,r,max(bm+1,tl),tr,value);
    }
}
ll findans(ll x,ll l,ll r,ll poz)
{
   //cout<<x<<" "<<l<<" "<<r<<" "<<t[x]<<endl;
    if (l==r)
        return t[x];
    else
    {
        ll bm=(l+r)/2;
        if (l<=poz && poz<=bm)
            return t[x]+findans(x*2,l,bm,poz);
        else return t[x]+findans(x*2+1,bm+1,r,poz);
    }
}
int main()
{
    ll n,m,i,j;
    cin>>n>>m;
    if (n==1)
    {
        ll x;
        cin>>x;
        for(i=1;i<=m;i++)
        {
            ll type;
            cin>>type;
            if (type==1)
            {
                cin>>x>>x;
            }
            else
            {
                ll H;
                cin>>H;
                if (H==x)
                    cout<<1<<endl;
                else cout<<0<<endl;
            }

        }
        return 0;
    }
    for(i=1;i<=n;i++)
        cin>>a[i];
    for(i=2;i<=n;i++)
        update(1,1,INF,min(a[i-1],a[i]),max(a[i-1],a[i]),1);
    //cout<<endl;
    for(i=1;i<=m;i++)
    {
        ll type;
        cin>>type;
        if (type==1)
        {
            ll x,y;
            cin>>x>>y;
            if (x!=1) update(1,1,INF,min(a[x-1],a[x]),max(a[x-1],a[x]),-1);
            if (x!=1) update(1,1,INF,min(a[x-1],y),max(a[x-1],y),1);
            if (x!=n) update(1,1,INF,min(a[x+1],a[x]),max(a[x+1],a[x]),-1);
            if (x!=n) update(1,1,INF,min(a[x+1],y),max(a[x+1],y),1);
            a[x]=y;
        }
        else
        {
            ll H;
            cin>>H;
            cout<<findans(1,1,INF,H)<<endl;
        }
    }
    return 0;
}

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:40:14: warning: unused variable 'j' [-Wunused-variable]
     ll n,m,i,j;
              ^

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