Submission #1128806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128806		icecream	Simple game (IZhO17_game)	C++20	0 / 100	23 ms	24644 KiB

game

//                                                             アイスクリーム                                                   
#include <bits/stdc++.h>
#ifndef alks
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#endif
#pragma GCC optimize("O3,unroll-loops")
#define ll long long
#define int ll
#define Yes cout<<"YES\n"; return;
#define No cout<<"NO\n"; return;
#define yes cout<<"Yes\n"; return;
#define no cout<<"No\n"; return;
#define wrans cout<<"-1\n"; return;
using namespace std;
const int N=1e6+100;
const int M=1e6+100;
const int mod1=998244353;
const int mod=1e9+7;
const int INF=1e18;
const long double eps=1e-12;
const string ab="abcdefghijklmnopqrstuvwxyz";
const string AB="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int n,q;
int a[N];
int t[N*4];
int cnt[N*4];
void push(int v,int tl, int tr){
    if(tl!=tr){
        cnt[v*2]+=cnt[v];
        cnt[v*2+1]+=cnt[v];
    }
    t[v]+=(tr-tl+1)*cnt[v];
    cnt[v]=0;
}
void upd(int v,int tl,int tr,int l,int r,int x){
    push(v,tl,tr);
    if(tl>r || tr<l){
        return;
    }
    if(l<=tl && tr<=r){
        cnt[v]+=x;
        push(v,tl,tr);
        return;
    }
    int mid=(tl+tr)>>1ll;
    upd(v*2,tl,mid,l,r,x);
    upd(v*2+1,mid+1,tr,l,r,x);
    t[v]=t[v*2]+t[v*2+1];
}
int get(int v,int tl,int tr,int l,int r){
    push(v,tl,tr);
    if(tl>r || tr<l){
        return 0ll;
    }
    if(l<=tl && tr<=r){
        return t[v];
    }
    int mid=(tl+tr)>>1ll;
    int sum=get(v*2,tl,mid,l,r);
    int sum1=get(v*2+1,mid+1,tr,l,r);
    return sum+sum1;
}
void alikosh(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=2;i<n;i++){
        upd(1,1,N,min(a[i],a[i+1]),max(a[i],a[i+1]),1);
        upd(1,1,N,min(a[i],a[i-1]),max(a[i],a[i-1]),1);
    }
    for(int t,pos,x;q--;){
        cin>>t;
        if(t==1){
            cin>>pos>>x;
            if(n==1){
                continue;
            }
            else if(pos==1){
                upd(1,1,N,min(a[pos],a[pos+1]),max(a[pos+1],a[pos]),-1);
                upd(1,1,N,a[pos],a[pos],-1);
                upd(1,1,N,min(x,a[pos+1]),max(a[pos+1],x),1);
                upd(1,1,N,x,x,1);
            }
            else if(pos==n){
                upd(1,1,N,min(a[pos-1],a[pos]),max(a[pos-1],a[pos]),-1);
                upd(1,1,N,a[pos],a[pos],-1);
                upd(1,1,N,min(x,a[pos-1]),max(a[pos-1],x),1);
                upd(1,1,N,x,x,1);
            }
            else{
                upd(1,1,N,min(a[pos-1],a[pos]),max(a[pos-1],a[pos]),-1);
                upd(1,1,N,min(a[pos],a[pos+1]),max(a[pos+1],a[pos]),-1);
                upd(1,1,N,min(x,a[pos+1]),max(a[pos+1],x),1);
                upd(1,1,N,min(x,a[pos-1]),max(a[pos-1],x),1);
            }
            continue;
        }
        cin>>x;
        cout<<get(1,1,N,x,x)<<'\n';
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int icecream1=1;
    // cin>>icecream1;   
    for(int i=1;i<=icecream1;i++){
        // cout<<"Case "<<i<<": ";
        alikosh();
    }
}
//, Ice \ \ 

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