Submission #91228

#	Time	Username	Problem	Language	Result	Execution time	Memory
91228		Abelyan	Simple game (IZhO17_game)	C++17	100 / 100	296 ms	11080 KiB

game

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;

#define fr first
#define sc second
#define FOR(i, a) for (int i = 0; i < (a); i++)
#define F0R(i, a, b) for (int i = (a); i <= (b); i++)
#define FORd(i,a) for (int i = (a)-1; i >= 0; i--)
#define F0Rd(i,a,b) for (int i = (b); i >= (a); i--)
#define trav(a, x) for (auto& a : x)

const int N=1000006;

int lazy[4*N];
int h[N];


void update(int v,int tl,int tr,int l,int r,ll del){
    if (l==INT_MAX || r==INT_MAX || l>r) return;
    if (tl==l && tr==r){
        lazy[v]+=del;
        return;
    }
    int tm=(tl+tr)/2;
    update(v+v,tl,tm,l,min(r,tm),del);
    update(v+v+1,tm+1,tr,max(tm+1,l),r,del);
}

int query(int v,int tl,int tr,int ind){
    if (ind==tl && ind==tr){
        return lazy[v];
    }
    int tm=(tl+tr)/2;
    if (ind<=tm)
        return query(v+v,tl,tm,ind)+lazy[v];
    return query(v+v+1,tm+1,tr,ind)+lazy[v];
}

int main(){
    ios_base::sync_with_stdio(false);
    //freopen("input.txt","r",stdin);
    int n,q;
    cin>>n>>q;
    h[0]=INT_MAX;
    F0R(i,1,n){
        cin>>h[i];
        update(1,0,N-1,min(h[i],h[i-1]),max(h[i],h[i-1]),1);
    }
    h[n+1]=INT_MAX;
    FOR(i,q){
        int type;
        cin>>type;
        if (type==1){
            int ind,hgh;
            cin>>ind>>hgh;
            update(1,0,N-1,min(h[ind],h[ind-1]),max(h[ind],h[ind-1]),-1);
            update(1,0,N-1,min(h[ind],h[ind+1]),max(h[ind],h[ind+1]),-1);
            h[ind]=hgh;
            update(1,0,N-1,min(h[ind],h[ind-1]),max(h[ind],h[ind-1]),1);
            update(1,0,N-1,min(h[ind],h[ind+1]),max(h[ind],h[ind+1]),1);
        }
        else{
            int hg;
            cin>>hg;
            cout<<query(1,0,N-1,hg)<<endl;
        }
    }
    return 0;
}

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