【題解】CSES 2425 Stack Weights

【題目敘述】https://cses.fi/problemset/task/2425/

#include <iostream>
using namespace std;
 
int n, c, s, mx[1000005], mn[1000005], lazy[1000005];
 
void push(int x, int l, int r){
    if (l == r || !lazy[x]) return;
    mx[x<<1] += lazy[x];
    mn[x<<1] += lazy[x];
    lazy[x<<1] += lazy[x];
    mx[x<<1|1] += lazy[x];
    mn[x<<1|1] += lazy[x];
    lazy[x<<1|1] += lazy[x];
    lazy[x] = 0;
}
 
void update(int x, int l, int r, int ul, int ur, int u){
    if (ul <= l && r <= ur){
        mx[x] += u;
        mn[x] += u;
        lazy[x] += u;
        return;
    }
    int mid = (l+r)/2;
    push(x, l, r);
    if (ul <= mid) update(x<<1, l, mid, ul, ur, u);
    if (ur > mid) update(x<<1|1, mid+1, r, ul, ur, u);
    mx[x] = max(mx[x<<1], mx[x<<1|1]);
    mn[x] = min(mn[x<<1], mn[x<<1|1]);
}
 
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> c >> s;
        if (s == 1) update(1, 1, n, 1, c, 1);
        if (s == 2) update(1, 1, n, 1, c, -1);
        if (mx[1] <= 0) cout << "<\n";
        else if (mn[1] >= 0) cout << ">\n";
        else cout << "?\n";
    }
}
分享本文 Share with friends