oj.uz

Submission #935454

# Submission time Handle Problem Language Result Execution time Memory
935454 2024-02-29T06:21:31 Z Darren0724 Simple game (IZhO17_game) C++17
0 / 100
 2 ms 8536 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-1)upd(p,-1);
            v[p]=x;
            if(p>1)upd(p-1,1);
            if(p<n-1)upd(p,1);
        }
        else{
            int p;cin>>p;
            cout<<bit.ask(p)<<endl;
        }
    }

    return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 2 ms 8236 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Incorrect 2 ms 8280 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 2 ms 8236 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Incorrect 2 ms 8280 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 2 ms 8236 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Incorrect 2 ms 8280 KB Output isn't correct
7 Halted 0 ms 0 KB -