oj.uz

Submission #83594

# Submission time Handle Problem Language Result Execution time Memory
83594 2018-11-09T12:50:18 Z ToadDaveski Simple game (IZhO17_game) C++14
100 / 100
 472 ms 35560 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;
        //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

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

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 15 ms 9796 KB Output is correct
3 Correct 13 ms 9796 KB Output is correct
4 Correct 14 ms 9796 KB Output is correct
5 Correct 14 ms 9796 KB Output is correct
6 Correct 14 ms 9936 KB Output is correct
7 Correct 7 ms 9936 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 15 ms 9796 KB Output is correct
3 Correct 13 ms 9796 KB Output is correct
4 Correct 14 ms 9796 KB Output is correct
5 Correct 14 ms 9796 KB Output is correct
6 Correct 14 ms 9936 KB Output is correct
7 Correct 7 ms 9936 KB Output is correct
8 Correct 252 ms 9936 KB Output is correct
9 Correct 406 ms 20832 KB Output is correct
10 Correct 412 ms 22632 KB Output is correct
11 Correct 252 ms 22632 KB Output is correct
12 Correct 324 ms 22632 KB Output is correct
13 Correct 292 ms 22632 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 15 ms 9796 KB Output is correct
3 Correct 13 ms 9796 KB Output is correct
4 Correct 14 ms 9796 KB Output is correct
5 Correct 14 ms 9796 KB Output is correct
6 Correct 14 ms 9936 KB Output is correct
7 Correct 7 ms 9936 KB Output is correct
8 Correct 252 ms 9936 KB Output is correct
9 Correct 406 ms 20832 KB Output is correct
10 Correct 412 ms 22632 KB Output is correct
11 Correct 252 ms 22632 KB Output is correct
12 Correct 324 ms 22632 KB Output is correct
13 Correct 292 ms 22632 KB Output is correct
14 Correct 453 ms 27860 KB Output is correct
15 Correct 431 ms 29920 KB Output is correct
16 Correct 472 ms 31968 KB Output is correct
17 Correct 421 ms 33520 KB Output is correct
18 Correct 455 ms 35560 KB Output is correct