oj.uz

Submission #83587

# Submission time Handle Problem Language Result Execution time Memory
83587 2018-11-09T12:24:21 Z ToadDaveski Simple game (IZhO17_game) C++14
0 / 100
 254 ms 263168 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 11 ms 6652 KB Output is correct
3 Correct 12 ms 6652 KB Output is correct
4 Runtime error 254 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 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 Correct 11 ms 6652 KB Output is correct
3 Correct 12 ms 6652 KB Output is correct
4 Runtime error 254 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 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 Correct 11 ms 6652 KB Output is correct
3 Correct 12 ms 6652 KB Output is correct
4 Runtime error 254 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -