oj.uz

Submission #598208

# Submission time Handle Problem Language Result Execution time Memory
598208 2022-07-17T19:36:01 Z reni Simple game (IZhO17_game) C++17
100 / 100
 79 ms 10204 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
long long a[1000001], fen[1000001];
void update(long long pos,long long val)
{
    for(int i=pos;i<=1000000;i+=(i&-i))
    {
        fen[i]+=val;
    }
}
long long query(long long val)
{
    long long sum=0;
    for(int i=val;i>0;i-=(i&-i))
    {
        sum+=fen[i];
    }
    return sum;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long i,j,n,m,t,pos,val;

    cin>>n>>m;

    for(i=1;i<=n;i++)
    {
        cin>>a[i];

        if(i!=1){
            update(min(a[i-1],a[i]),1);
            update(max(a[i-1],a[i]),-1);
        }
    }

    for(i=1;i<=m;i++)
    {
        cin>>t;

        if(t==1)
        {
            cin>>pos>>val;

            if(pos>1)
            {
                update(min(a[pos-1],a[pos]),-1);
                update(max(a[pos-1],a[pos]),1);
                update(min(a[pos-1],val),1),
                update(max(a[pos-1],val),-1);
            }
            if(pos<n)
            {
                update(min(a[pos+1],a[pos]),-1);
                update(max(a[pos+1],a[pos]),1);
                update(min(a[pos+1],val),1),
                update(max(a[pos+1],val),-1);
            }
            a[pos]=val;
        }
        else
        {
            cin>>val;
            cout<<query(val)<<endl;
        }
    }

}

Compilation message

game.cpp: In function 'int main()':
game.cpp:27:17: warning: unused variable 'j' [-Wunused-variable]
   27 |     long long i,j,n,m,t,pos,val;
      |                 ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 4 ms 6864 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 2 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 4 ms 6864 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 2 ms 340 KB Output is correct
8 Correct 39 ms 2060 KB Output is correct
9 Correct 57 ms 10204 KB Output is correct
10 Correct 48 ms 10192 KB Output is correct
11 Correct 30 ms 2024 KB Output is correct
12 Correct 36 ms 2736 KB Output is correct
13 Correct 47 ms 2452 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 4 ms 6864 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 2 ms 340 KB Output is correct
8 Correct 39 ms 2060 KB Output is correct
9 Correct 57 ms 10204 KB Output is correct
10 Correct 48 ms 10192 KB Output is correct
11 Correct 30 ms 2024 KB Output is correct
12 Correct 36 ms 2736 KB Output is correct
13 Correct 47 ms 2452 KB Output is correct
14 Correct 71 ms 9896 KB Output is correct
15 Correct 68 ms 9928 KB Output is correct
16 Correct 76 ms 9928 KB Output is correct
17 Correct 78 ms 9872 KB Output is correct
18 Correct 79 ms 9984 KB Output is correct