oj.uz

Submission #426680

# Submission time Handle Problem Language Result Execution time Memory
426680 2021-06-14T08:57:38 Z MOUF_MAHMALAT Simple game (IZhO17_game) C++14
0 / 100
 2 ms 332 KB 
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
using namespace std;
typedef int ll;
ll n,q,t,a[1000009],p[4000009],lz[4000009];
void push(ll d,ll l,ll r)
{
    p[d]+=lz[d];
    if(l<r)
    {
        lz[d*2]+=lz[d];
        lz[d*2+1]+=lz[d];
    }
    lz[d]=0;
}
void up(ll d,ll l,ll r,ll x,ll y,ll val)
{
    push(d,l,r);
    if(r<x||l>y||y<x)
        return;
    if(x<=l&&y>=r)
    {
        lz[d]+=val;
        push(d,l,r);
        return;
    }
    ll m=(l+r)/2,i=d*2;
    up(i,l,m,x,y,val),up(i+1,m+1,r,x,y,val);
    p[d]=p[i]+p[i+1];
}
void best(ll d,ll l,ll r,ll x)
{
    push(d,l,r);
    if(l==r)
    {
        cout<<p[l]<<endl;
        return;
    }
    ll m=(l+r)/2,i=d*2;
    if(x<=m)
        best(i,l,m,x);
    else
        best(i+1,m+1,r,x);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(ll i=1; i<=n; i++)
        cin>>a[i];
    for(ll i=2; i<=n; i++)
    {
        ll x=a[i-1],y=a[i];
        if(x>y)
            swap(x,y);
        up(1,1,n,x,y,1);
        if(i<n)
            up(1,1,n,a[i],a[i],-1);
    }
    while(q--)
    {
        cin>>t;
        if(t==1)
        {
            ll id,pos,x,y;
            cin>>id>>pos;
            if(id>1)
            {
                x=a[id-1],y=a[id];
                if(x>y)
                    swap(x,y);
                up(1,1,n,x,y,-1);
                x=a[id-1],y=pos;
                if(x>y)
                    swap(x,y);
                up(1,1,n,x,y,1);
            }
            if(id<n)
            {
                x=a[id],y=a[id+1];
                if(x>y)
                    swap(x,y);
                up(1,1,n,x,y,-1);
                x=pos,y=a[id+1];
                if(x>y)
                    swap(x,y);
                up(1,1,n,x,y,1);
            }
            a[id]=pos;
        }
        else
        {
            ll id;
            cin>>id;
            best(1,1,n,id);
        }
    }
    return 0;
}

Subtask #1
0 / 22.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 51.0

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