Submission #1356640

#TimeUsernameProblemLanguageResultExecution timeMemory
1356640nathlol2돌 무게 재기 (IZhO11_stones)C++20
100 / 100
24 ms3676 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, INF = 1e9;
int n;

struct lazyseg{
    struct node{
        int mn, mx, lz;
    }seg[4 * N];
    void push(int nd, int l, int r){
        if(seg[nd].lz != 0){
            seg[nd].mn += seg[nd].lz;
            seg[nd].mx += seg[nd].lz;
            if(l != r){
                seg[nd * 2].lz += seg[nd].lz;
                seg[nd * 2 + 1].lz += seg[nd].lz;
            }
            seg[nd].lz = 0;
        }
    }
    node merge(node lhs, node rhs){
        node res;
        res.mn = min(lhs.mn, rhs.mn);
        res.mx = max(lhs.mx, rhs.mx);
        return res;
    }
    void upd(int nd, int l, int r, int ql, int qr, int x){
        push(nd, l, r);
        if(qr < l || r < ql) return;
        if(ql <= l && r <= qr){
            seg[nd].lz += x;
            push(nd, l, r);
            return;
        }
        int md = (l + r) / 2;
        upd(nd * 2, l, md, ql, qr, x);
        upd(nd * 2 + 1, md + 1, r, ql, qr, x);
        seg[nd] = merge(seg[nd * 2], seg[nd * 2 + 1]);
    }
    node qry(int nd, int l, int r, int ql, int qr){
        push(nd, l, r);
        if(qr < l || r < ql) return {INF, -INF, 0};
        if(ql <= l && r <= qr) return seg[nd];
        int md = (l + r) / 2;
        return merge(qry(nd * 2, l, md, ql, qr), qry(nd * 2 + 1, md + 1, r, ql, qr));
    }
}s;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i = 1;i<=n;i++){
        int x, r; cin >> x >> r;
        if(r == 1){
            s.upd(1, 1, n, 1, x, 1);
        }else{
            s.upd(1, 1, n, 1, x, -1);
        }
        lazyseg::node v = s.qry(1, 1, n, 1, n);
        if(v.mn >= 0) cout << ">\n";
        else if(v.mx <= 0) cout << "<\n";
        else cout << "?\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...