oj.uz

Submission #598182

# Submission time Handle Problem Language Result Execution time Memory
598182 2022-07-17T18:54:03 Z daisy2 Simple game (IZhO17_game) C++14
100 / 100
 77 ms 11144 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<=1000000;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
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 6792 KB Output is correct
3 Correct 4 ms 6612 KB Output is correct
4 Correct 3 ms 6740 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 3 ms 6868 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 6792 KB Output is correct
3 Correct 4 ms 6612 KB Output is correct
4 Correct 3 ms 6740 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 3 ms 6868 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 34 ms 2124 KB Output is correct
9 Correct 46 ms 11080 KB Output is correct
10 Correct 48 ms 11104 KB Output is correct
11 Correct 31 ms 1980 KB Output is correct
12 Correct 45 ms 3256 KB Output is correct
13 Correct 46 ms 3268 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 6792 KB Output is correct
3 Correct 4 ms 6612 KB Output is correct
4 Correct 3 ms 6740 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 3 ms 6868 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 34 ms 2124 KB Output is correct
9 Correct 46 ms 11080 KB Output is correct
10 Correct 48 ms 11104 KB Output is correct
11 Correct 31 ms 1980 KB Output is correct
12 Correct 45 ms 3256 KB Output is correct
13 Correct 46 ms 3268 KB Output is correct
14 Correct 66 ms 11144 KB Output is correct
15 Correct 66 ms 11116 KB Output is correct
16 Correct 65 ms 11132 KB Output is correct
17 Correct 68 ms 11044 KB Output is correct
18 Correct 77 ms 11076 KB Output is correct