Submission #1135615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135615		imarn	Simple game (IZhO17_game)	C++20	100 / 100	43 ms	9028 KiB

game

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
const int mxn=1e6+5;
ll fw[mxn]{0};
void add(int i,int amt){
    for(;i<mxn;i+=i&-i)fw[i]+=amt;
}
int qr(int i,int rs=0){
    for(;i;i-=i&-i)rs+=fw[i];
    return rs;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;
    int a[n+1];
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=2;i<=n;i++){
        int l=min(a[i-1],a[i]),r=max(a[i-1],a[i]);
        add(l,1);add(r+1,-1);
    }
    while(m--){
        int o;cin>>o;
        if(o==1){
            int i,x,l,r;cin>>i>>x;
            if(i!=1){
                l=min(a[i-1],a[i]);r=max(a[i-1],a[i]);
                add(l,-1);add(r+1,1);
                l=min(a[i-1],x);r=max(a[i-1],x);
                add(l,1);add(r+1,-1);
            }
            if(i!=n){
                l=min(a[i+1],a[i]);r=max(a[i+1],a[i]);
                add(l,-1);add(r+1,1);
                l=min(a[i+1],x);r=max(a[i+1],x);
                add(l,1);add(r+1,-1);
            }a[i]=x;
        }
        else {
            int x;cin>>x;
            cout<<qr(x)<<'\n';
        }
    }
}

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