Submission #1173304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173304		dbekarys	Simple game (IZhO17_game)	C++20	100 / 100	411 ms	34488 KiB

game

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define pll pair<long long,long long>
#define int long long
using namespace std;
/*using namespace __gnu_pbds; 
template<class T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
const int mod=1e9+7;
const int N=1e6+1;
const long long inf=1e18;

int a[N],t[N*4],add[N*4];
void push( int v, int tl, int tr )
{
    if( add[v] == 0 ) return;
    t[v] += (tr - tl + 1) * add[v];
    if( tl < tr )
    {
        add[v + v] += add[v];
        add[v + v + 1] += add[v];
    }
    add[v] = 0;
}
void up(int x,int l,int r,int ll,int rr,int v){
    push(x,l,r);
    if(l>rr || r<ll){
        return;
    }
    if(ll<=l && r<=rr){
        add[x]+=v;
        push(x,l,r);
        return;
    }
    int m=(l+r)/2;
    up(x+x,l,m,ll,rr,v);
    up(x+x+1,m+1,r,ll,rr,v);
}
int get(int x,int l,int r,int pos){
    push(x,l,r);
    if(l==r) return t[x];
    int m=(l+r)/2;
    if(pos<=m) return get(x+x,l,m,pos);
    else return get(x+x+1,m+1,r,pos);
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie();
    
    int n,k;
    cin>> n>>k;
    int a[n+1];
    for(int i=1;i<=n;i++){
        cin>> a[i];
        if( i > 1 )
            up(1, 1, N - 1, min(a[i - 1], a[i]), max(a[i - 1], a[i]), 1);
    }
    for(int j=0;j<k;j++){
        int t;
        cin>> t;
        if(t==1){
            int i,v;
            cin>> i>>v;
            if( i > 1 )
            {
                up(1, 1, N - 1, min(a[i - 1], a[i]), max(a[i - 1], a[i]), -1);
                up(1, 1, N - 1, min(a[i - 1], v), max(a[i - 1], v), 1);
            }
            if( i < n )
            {
                up(1, 1, N - 1, min(a[i], a[i + 1]), max(a[i], a[i + 1]), -1);
                up(1, 1, N - 1, min(v, a[i + 1]), max(v, a[i + 1]), 1);
            }
            a[i] = v;
        }
        else {
            int i;
            cin>> i;
            cout<< get(1,1,N-1,i)<<endl;
        }
    }
}

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