Submission #1220944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220944		AlgorithmWarrior	Simple game (IZhO17_game)	C++20	100 / 100	43 ms	5188 KiB

game

#include <bits/stdc++.h>

using namespace std;

int const HMAX=1000005;
int const NMAX=100005;
int n,q;
int v[NMAX];

int ub(int x){
    return x&(-x);
}

struct fenwick_tree{
    int v[HMAX];
    void add(int pos,int val){
        while(pos<HMAX){
            v[pos]+=val;
            pos+=ub(pos);
        }
    }
    int sum(int pos){
        int s=0;
        while(pos){
            s+=v[pos];
            pos-=ub(pos);
        }
        return s;
    }
    void add_range(int l,int r,int val){
        if(l>r)
            swap(l,r);
        add(l,val);
        add(r+1,-val);
    }
}aib;

void read(){
    cin>>n>>q;
    int i;
    for(i=1;i<=n;++i)
        cin>>v[i];
}

void init(){
    int i;
    for(i=1;i<n;++i)
        aib.add_range(v[i],v[i+1],1);
}

void process_queries(){
    while(q--){
        int type;
        cin>>type;
        if(type==1){
            int pos,val;
            cin>>pos>>val;
            if(pos>1){
                aib.add_range(v[pos-1],v[pos],-1);
                aib.add_range(v[pos-1],val,1);
            }
            if(pos<n){
                aib.add_range(v[pos],v[pos+1],-1);
                aib.add_range(val,v[pos+1],1);
            }
            v[pos]=val;
        }
        else{
            int val;
            cin>>val;
            cout<<aib.sum(val)<<'\n';
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read();
    init();
    process_queries();
    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51