oj.uz

Submission #83582

# Submission time Handle Problem Language Result Execution time Memory
83582 2018-11-09T12:18:22 Z ToadDaveski Simple game (IZhO17_game) C++14
0 / 100
 12 ms 9412 KB 
#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;
        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)
{
    if (l==r)
        return t[x];
    else
    {
        ll bm=(l+r)/2;
        if (l<=poz && poz<=r)
            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;
                else cout<<0;
            }

        }
        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<<3;
    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,a[x-1],a[x],-1);
            if (x!=1) update(1,1,INF,a[x-1],y,1);
            if (x!=n) update(1,1,INF,a[x],a[x+1],-1);
            if (x!=n) update(1,1,INF,y,a[x+1],1);
            a[x]=y;
        }
        else
        {
            ll H;
            cin>>H;
            cout<<findans(1,1,INF,H)<<endl;
        }
    }
    return 0;
}

Compilation message

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

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 12 ms 9412 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 12 ms 9412 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 12 ms 9412 KB Output isn't correct
3 Halted 0 ms 0 KB -