oj.uz

Submission #915507

# Submission time Handle Problem Language Result Execution time Memory
915507 2024-01-24T05:18:12 Z vjudge1 Simple game (IZhO17_game) C++17
100 / 100
 460 ms 36852 KB 
/*#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 11 ms 34396 KB Output is correct
3 Correct 12 ms 33116 KB Output is correct
4 Correct 12 ms 34140 KB Output is correct
5 Correct 11 ms 34208 KB Output is correct
6 Correct 12 ms 33216 KB Output is correct
7 Correct 8 ms 35420 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 11 ms 34396 KB Output is correct
3 Correct 12 ms 33116 KB Output is correct
4 Correct 12 ms 34140 KB Output is correct
5 Correct 11 ms 34208 KB Output is correct
6 Correct 12 ms 33216 KB Output is correct
7 Correct 8 ms 35420 KB Output is correct
8 Correct 192 ms 11492 KB Output is correct
9 Correct 317 ms 36852 KB Output is correct
10 Correct 311 ms 36692 KB Output is correct
11 Correct 191 ms 9804 KB Output is correct
12 Correct 242 ms 14160 KB Output is correct
13 Correct 216 ms 36688 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 11 ms 34396 KB Output is correct
3 Correct 12 ms 33116 KB Output is correct
4 Correct 12 ms 34140 KB Output is correct
5 Correct 11 ms 34208 KB Output is correct
6 Correct 12 ms 33216 KB Output is correct
7 Correct 8 ms 35420 KB Output is correct
8 Correct 192 ms 11492 KB Output is correct
9 Correct 317 ms 36852 KB Output is correct
10 Correct 311 ms 36692 KB Output is correct
11 Correct 191 ms 9804 KB Output is correct
12 Correct 242 ms 14160 KB Output is correct
13 Correct 216 ms 36688 KB Output is correct
14 Correct 440 ms 36420 KB Output is correct
15 Correct 460 ms 36436 KB Output is correct
16 Correct 450 ms 36432 KB Output is correct
17 Correct 444 ms 36780 KB Output is correct
18 Correct 446 ms 36280 KB Output is correct