oj.uz

Submission #935456

# Submission time Handle Problem Language Result Execution time Memory
935456 2024-02-29T06:30:12 Z Darren0724 Simple game (IZhO17_game) C++17
100 / 100
 54 ms 11260 KB 
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define int long long
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=1000005;
const int INF=1e18;
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 1 ms 8280 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 2 ms 8168 KB Output is correct
4 Correct 2 ms 8284 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8284 KB Output is correct
7 Correct 2 ms 8284 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8280 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 2 ms 8168 KB Output is correct
4 Correct 2 ms 8284 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8284 KB Output is correct
7 Correct 2 ms 8284 KB Output is correct
8 Correct 31 ms 9820 KB Output is correct
9 Correct 38 ms 11160 KB Output is correct
10 Correct 42 ms 11092 KB Output is correct
11 Correct 34 ms 9808 KB Output is correct
12 Correct 32 ms 11004 KB Output is correct
13 Correct 36 ms 11092 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8280 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 2 ms 8168 KB Output is correct
4 Correct 2 ms 8284 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8284 KB Output is correct
7 Correct 2 ms 8284 KB Output is correct
8 Correct 31 ms 9820 KB Output is correct
9 Correct 38 ms 11160 KB Output is correct
10 Correct 42 ms 11092 KB Output is correct
11 Correct 34 ms 9808 KB Output is correct
12 Correct 32 ms 11004 KB Output is correct
13 Correct 36 ms 11092 KB Output is correct
14 Correct 54 ms 11236 KB Output is correct
15 Correct 50 ms 11108 KB Output is correct
16 Correct 52 ms 11260 KB Output is correct
17 Correct 46 ms 11092 KB Output is correct
18 Correct 51 ms 11092 KB Output is correct