Submission #577510

#	Time	Username	Problem	Language	Result	Execution time	Memory
577510		gg123_pe	Simple game (IZhO17_game)	C++14	0 / 100	4 ms	6588 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; 
    if(i+1 <= n){
        x = min(a[i], a[i+1]), y = max(a[i], a[i+1]); 
        L.upd(x, k);
        R.upd(y, k);         
    }
    if(i-1 >= 1){
        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+1){
        int x, y; 
        go(i, 1); 
    }

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

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

            go(i, -1); 

            a[i] = val; 

            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; 
}

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:52:13: warning: unused variable 'x' [-Wunused-variable]
   52 |         int x, y;
      |             ^
game.cpp:52:16: warning: unused variable 'y' [-Wunused-variable]
   52 |         int x, y;
      |                ^

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