oj.uz

Submission #935750

# Submission time Handle Problem Language Result Execution time Memory
935750 2024-02-29T13:31:59 Z Darren0724 Simple game (IZhO17_game) C++17
100 / 100
 45 ms 7000 KB 
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=1000005;
struct BIT{
    vector<int> v;
    int n;
    BIT(int n1){
        n=n1;
        v.resize(n+1);
    }
    void add(int p,int x){
        for(int i=p;i<=n;i+=i&(-i)){
            v[i]+=x;
        }
    }
    int ask(int p){
        int ans=0;
        for(int i=p;i>0;i-=i&(-i)){
            ans+=v[i];
        }
        return ans;
    }
};
int32_t main() {
    LCBorz;
    int n,q;cin>>n>>q;
    vector<int> v(n+1);
    BIT bit(N);
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    auto upd=[&](int i,int c){
        int a=min(v[i],v[i+1]),b=max(v[i],v[i+1]);
        bit.add(a,c);
        bit.add(b+1,-c);
    };  
    for(int i=1;i<n;i++){
        upd(i,1);
    }
    for(int i=0;i<q;i++){
        int id;cin>>id;
        if(id==1){
            int p,x;cin>>p>>x;
            if(p>1)upd(p-1,-1);
            if(p<n)upd(p,-1);
            v[p]=x;
            if(p>1)upd(p-1,1);
            if(p<n)upd(p,1);
        }
        else{
            int p;cin>>p;
            cout<<bit.ask(p)<<endl;
        }
    }
 
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 30 ms 5724 KB Output is correct
9 Correct 35 ms 6740 KB Output is correct
10 Correct 31 ms 7000 KB Output is correct
11 Correct 31 ms 5584 KB Output is correct
12 Correct 32 ms 6492 KB Output is correct
13 Correct 31 ms 6736 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 30 ms 5724 KB Output is correct
9 Correct 35 ms 6740 KB Output is correct
10 Correct 31 ms 7000 KB Output is correct
11 Correct 31 ms 5584 KB Output is correct
12 Correct 32 ms 6492 KB Output is correct
13 Correct 31 ms 6736 KB Output is correct
14 Correct 39 ms 6736 KB Output is correct
15 Correct 39 ms 6736 KB Output is correct
16 Correct 40 ms 6748 KB Output is correct
17 Correct 41 ms 6744 KB Output is correct
18 Correct 45 ms 6916 KB Output is correct