Submission #1042714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042714		fryingduc	Simple game (IZhO17_game)	C++17	100 / 100	48 ms	15520 KiB

game

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

const int maxn = 1e6 + 6;
int n, q, h[maxn];
int mn[maxn], mx[maxn];
pair<int, int> a[maxn];

struct fenwick_tree {
    #define gb(x) (x) & (-x)
    int n;
    vector<int> bit;
    fenwick_tree() {}
    fenwick_tree(int n) : n(n), bit(n + 5) {}
    void update(int x, int val) {
        if(x <= 0) return;
        for(int i = x; i <= n; i += gb(i)) bit[i] += val;
    }
    int get(int x) {
        int ans = 0;
        for(int i = x; i > 0; i -= gb(i)) ans += bit[i];
        return ans;
    }
    int get(int l, int r) {
        return get(r) - get(l - 1);
    }
} fen_mn, fen_mx;
void update(int p) {
    fen_mx.update(mx[p], -1);
    fen_mn.update(mn[p], -1);
    
    mx[p] = max(a[p].first, a[p].second);
    mn[p] = min(a[p].first, a[p].second);
    
    fen_mx.update(mx[p], 1);
    fen_mn.update(mn[p], 1);
}
void solve() {
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) {
        cin >> h[i];
    }
    fen_mx = fenwick_tree(maxn);
    fen_mn = fenwick_tree(maxn);
    for(int i = 1; i < n; ++i) {
        a[i] = {h[i], h[i + 1]};
        update(i);        
    }
    while(q--) {
        int op; cin >> op;
        if(op == 1) {
            int p, val; cin >> p >> val;
            if(p < n) {
                a[p].first = val;
                update(p);
            }
            if(p > 1) {
                a[p - 1].second = val;
                update(p - 1);
            }
        }
        else {
            int height; cin >> height;
            
            int x = n - 1 - fen_mn.get(height, maxn) - fen_mx.get(height);
            
            cout << x << '\n';
        }
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}
/*
3 3
1 5 1
2 3
1 1 5
2 3
*/

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