oj.uz

답안 #1042709

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1042709 2024-08-03T09:55:41 Z fryingduc Simple game (IZhO17_game) C++17
0 / 100
 2 ms 10332 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];
    }
    for(int i = 1; i < n; ++i) {
        a[i] = {h[i], h[i + 1]};
        update(i);        
    }
    fen_mx = fenwick_tree(maxn);
    fen_mn = fenwick_tree(maxn);
    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 + 1, maxn) - fen_mx.get(height - 1);
            
            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
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10192 KB Output is correct
2 Incorrect 2 ms 10332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10192 KB Output is correct
2 Incorrect 2 ms 10332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10192 KB Output is correct
2 Incorrect 2 ms 10332 KB Output isn't correct
3 Halted 0 ms 0 KB -