oj.uz

Submission #1042714

# Submission time Handle Problem Language Result Execution time Memory
1042714 2024-08-03T09:57:43 Z fryingduc Simple game (IZhO17_game) C++17
100 / 100
 48 ms 15520 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10332 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 3 ms 10208 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 2 ms 10328 KB Output is correct
6 Correct 2 ms 10332 KB Output is correct
7 Correct 2 ms 10332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10332 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 3 ms 10208 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 2 ms 10328 KB Output is correct
6 Correct 2 ms 10332 KB Output is correct
7 Correct 2 ms 10332 KB Output is correct
8 Correct 31 ms 14180 KB Output is correct
9 Correct 34 ms 15388 KB Output is correct
10 Correct 34 ms 15404 KB Output is correct
11 Correct 28 ms 14088 KB Output is correct
12 Correct 31 ms 15196 KB Output is correct
13 Correct 30 ms 15440 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10332 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 3 ms 10208 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 2 ms 10328 KB Output is correct
6 Correct 2 ms 10332 KB Output is correct
7 Correct 2 ms 10332 KB Output is correct
8 Correct 31 ms 14180 KB Output is correct
9 Correct 34 ms 15388 KB Output is correct
10 Correct 34 ms 15404 KB Output is correct
11 Correct 28 ms 14088 KB Output is correct
12 Correct 31 ms 15196 KB Output is correct
13 Correct 30 ms 15440 KB Output is correct
14 Correct 42 ms 15420 KB Output is correct
15 Correct 41 ms 15404 KB Output is correct
16 Correct 48 ms 15520 KB Output is correct
17 Correct 41 ms 15352 KB Output is correct
18 Correct 42 ms 15504 KB Output is correct