oj.uz

Submission #598180

# Submission time Handle Problem Language Result Execution time Memory
598180 2022-07-17T18:51:12 Z daisy2 Simple game (IZhO17_game) C++14
0 / 100
 1 ms 340 KB 
#include<bits/stdc++.h>
#include<vector>
#define endl '\n'
using namespace std;
long long n,h[100005],fenwick[1000005],m,t,num,p;
void upd(long long x,long long val)
{
    for(int i=x;i<=n;i += i& -i)
    {
        fenwick[i]+=val;
    }
}
void update(long long a,long long b,long long v)
{
    if(a>b) swap(a,b);
    upd(a,v);
    upd(b,-v);
}
long long query(long long x)
{
    long long r=0;
    for(long long i=x;i>0; i-= i & -i)
    {
        r+=fenwick[i];
    }
    return r;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;

    cin>>h[1];
    for(int i=2;i<=n;i++)
    {
        cin>>h[i];
        update(h[i-1],h[i],1);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>t>>num;
        if(t==1)
        {
            cin>>p;
            if(num>1){
                update(h[num-1],h[num],-1);
                update(h[num-1],p,1);
            }

            if(num<n){
                update(h[num],h[num+1],-1);
                update(p,h[num+1],1);
            }
            h[num]=p;
            continue;
        }
        cout<<query(num)<<endl;
    }

}

Subtask #1
0 / 22.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 51.0

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