Submission #173212

#	Time	Username	Problem	Language	Result	Execution time	Memory
173212		achibasadzishvili	Simple game (IZhO17_game)	C++14	100 / 100	383 ms	11128 KiB

game

#include<bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
using namespace std;
ll n,pown = 1,a[500006],m,typ,t[5000005],r,l,ad;
void upd(ll x,ll L,ll R){
    if(L > r || R < l)return;
    if(L >= l && R <= r){
        t[x] += ad;
        return;
    }
    t[2 * x] += t[x];
    t[2 * x + 1] += t[x];
    t[x] = 0;
    upd(2 * x,L,(L+R)/2);
    upd(2 * x + 1,(L+R)/2+1,R);
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    
    while(pown <= 1000005)
        pown *= 2;
    
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    
    for(int i=2; i<=n; i++){
        l = min(a[i - 1] , a[i]);
        r = max(a[i - 1] , a[i]);
        ad = 1;
        upd(1 , 1 , pown);
    }
    
    while(m--){
        cin >> typ;
        if(typ == 1){
            int x,y;
            cin >> x >> y;
            if(x > 1){
                l = min(a[x - 1] , a[x]);
                r = max(a[x - 1] , a[x]);
                ad = -1;
                upd(1 , 1 , pown);
            }
            if(x < n){
                l = min(a[x + 1] , a[x]);
                r = max(a[x + 1] , a[x]);
                ad = -1;
                upd(1 , 1 , pown);
            }
            a[x] = y;
            if(x > 1){
                l = min(a[x - 1] , a[x]);
                r = max(a[x - 1] , a[x]);
                ad = 1;
                upd(1 , 1 , pown);
            }
            if(x < n){
                l = min(a[x + 1] , a[x]);
                r = max(a[x + 1] , a[x]);
                ad = 1;
                upd(1 , 1 , pown);
            }
        }
        else {
            int x;
            cin >> x;
            ll ans = 0;
            x = pown + x - 1;
            while(x){
                ans += t[x];
                x /= 2;
            }
            cout << ans << '\n';
        }
    }
    
    
    
    
    return 0;
}

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