Submission #577512

#	Time	Username	Problem	Language	Result	Execution time	Memory
577512		gg123_pe	Simple game (IZhO17_game)	C++14	100 / 100	251 ms	10764 KiB

game

#include <bits/stdc++.h>
using namespace std; 

typedef long long ll; 
#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)

const int N = 1e5 + 5, M = 1e6 + 5, mod = 1e9 + 7; 


int n, m, a[N]; 

struct bit{
    int bit[M]; 

    void upd(int x, int val){
        for(; x < M; x = (x|(x+1))) bit[x] += val;
    }

    int get(int x){
        int ans = 0;
        for(; x >= 0; x = (x&(x+1)) - 1) ans += bit[x];  
        return ans; 
    }

    int que(int l, int r){
        return get(r) - get(l-1); 
    }

}L, R; 


void go(int i, int k){
    int x, y; 
    x = min(a[i], a[i+1]), y = max(a[i], a[i+1]); 
    L.upd(x, k);        
    R.upd(y, k);         
}

int main(){
    cin >> n >> m; 

    f(i,1,n+1) cin >> a[i]; 

    f(i,1,n){
        go(i, 1); 
    }

    while(m--){
        int t, i, val; cin >> t;

        if(t == 1){
            cin >> i >> val; 

            if(i >= 2) go(i-1, -1);
            if(i <= n-1) go(i, -1); 

            a[i] = val; 

            if(i >= 2) go(i-1, 1); 
            if(i <= n-1) go(i, 1); 
        }
        else{
            cin >> i; 

            int ans = n-1; 

            ans -= (L.que(i+1, M-1) + R.que(0, i-1));
        
            cout << ans << "\n"; 
        }
    }
    return 0; 
}

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