Submission #1135991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135991		adilet_321	Simple game (IZhO17_game)	C++20	100 / 100	360 ms	34628 KiB

game

/*#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")*/
#include <bits/stdc++.h>
#include <iomanip>
#define ll long long
#define int long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define str string
#define pii pair<int,int>
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define mii map<int,int>
#define mll map<ll,ll>
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
#define yess cout<<"Yes\n";
#define noo cout<<"No\n";
using namespace std;

int t[4000001],s=0,u[4000001];

void pp(int v,int tl,int tr){
    if(u[v]==0)return;
    t[v]+=(tr-tl+1)*u[v];
    //cout<<tl<<" "<<tr<<" "<<t[v]<<"\n";
    if(tl!=tr){
        u[v+v]+=u[v];
        u[v+v+1]+=u[v];
    }
    u[v]=0;
}

void get(int v,int tl,int tr,int p){
    pp(v,tl,tr);
    if(tl==tr){
        //cout<<tl<<" "<<t[v]<<" ";
        s+=t[v];
        return;
    }
    pp(v,tl,tr);
    int tm=(tl+tr)>>1;
    if(p<=tm)get(v+v,tl,tm,p);
    else get(v+v+1,tm+1,tr,p);
}

void upd(int v,int tl,int tr,int l,int r,int x){
    pp(v,tl,tr);
    if(tl>=l && tr<=r){
        //cout<<t[v]<<" "<<tl<<" "<<tr<<" "<<x<<"\n";
        u[v]+=x;
        pp(v,tl,tr);
        //cout<<t[v]<<" "<<tl<<" "<<tr<<" "<<x<<"\n";
        return;
    }
    if(tl>r || tr<l){
        return;
    }
    pp(v,tl,tr);
    int tm=(tl+tr)>>1;
    upd(v+v,tl,tm,l,r,x);
    upd(v+v+1,tm+1,tr,l,r,x);
    t[v]=t[v+v]+t[v+v+1];
}

void solve(){
    int n,m;
    cin>>n>>m;
    int a[n+3];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=2;i<=n;i++){
        //cout<<min(a[i-1],a[i])<<" "<<max(a[i-1],a[i])<<"\n";
        upd(1,1,1000000,min(a[i-1],a[i]),max(a[i-1],a[i]),1);
    }
    for(int i=1;i<=m;i++){
        int tt;
        cin>>tt;
        if(tt==1){
            int p,v;
            cin>>p>>v;
            if(p>1)upd(1,1,1000000,min(a[p-1],a[p]),max(a[p-1],a[p]),-1);
            if(p<n)upd(1,1,1000000,min(a[p],a[p+1]),max(a[p],a[p+1]),-1);
            if(p>1)upd(1,1,1000000,min(a[p-1],v),max(a[p-1],v),1);
            if(p<n)upd(1,1,1000000,min(v,a[p+1]),max(v,a[p+1]),1);
            a[p]=v;
        }
        else{
            int h;
            cin>>h;
            s=0;
            get(1,1,1000000,h);
            cout<<s<<"\n";
        }
    }
}

signed main(){
	//ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	//srand( time(0));
	//rand()
	//freopen("game.in", "r", stdin);
	//freopen("game.out", "w", stdout);
    int tests=1;
    //cin>>tests;
    for(int i=1;i<=tests;i++){
		//cout<<"TEST CASE : "<<i<<"\n";
		solve();
	}
}

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