Submission #1128745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128745		icecream	Simple game (IZhO17_game)	C++20	22 / 100	1090 ms	3332 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 f(int a,int b,int ans){
    if(a<ans && b>ans){
        return 1;
    }
    if(a>ans && b<ans){
        return 1;
    }
    return 0;
}
void build(int v,int tl,int tr){
    if(tl==tr){
        t[v]=0;
        return;
    }
    int mid=(tl+tr)>>1ll;
    build(v*2,tl,mid);
    build(v*2+1,mid+1,tr);
    t[v]=(t[v*2]+t[v*2+1]);
}
void upd(int v,int tl,int tr,int pos,int x){
    if(tl==tr){
        t[v]=f(a[tl],a[tl+1],x);
        return;
    }
    int mid=(tl+tr)>>1ll;
    if(pos<=mid){
        upd(v*2,tl,mid,pos,x);
    }
    else{
        upd(v*2+1,mid+1,tr,pos,x);
    }
    t[v]=(t[v*2]+t[v*2+1]);
}
int get(int v,int tl,int tr,int l,int r){
    if(tl>r || tr<l){
        return 0ll;
    }
    if(l<=tl && r>=tr){
        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];
    }
    build(1,1,n-1);
    for(int t,pos,x;q--;){
        cin>>t;
        if(t==1){
            cin>>pos>>x;
            a[pos]=x;
            if(pos>1){
                upd(1,1,n-1,pos-1,x);
            }
            if(pos<n){
                upd(1,1,n-1,pos,x);
            }
            upd(1,1,n-1,pos,x);
            continue;
        }
        cin>>x;
        int sum=0;
        for(int i=1;i<n;i++){
            sum+=f(a[i],a[i+1],x);
        }
        cout<<sum<<"\n";
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int alikosh1=1;
    // cin>>alikosh1;   
    for(int i=1;i<=alikosh1;i++){
        // cout<<"Case "<<i<<": ";
        alikosh();
    }
}
//, Ice \ \ 

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