Submission #935750

#	Time	Username	Problem	Language	Result	Execution time	Memory
935750		Darren0724	Simple game (IZhO17_game)	C++17	100 / 100	45 ms	7000 KiB

game

#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 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51