Submission #1074752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074752		coolboy19521	Weighting stones (IZhO11_stones)	C++17	0 / 100	1 ms	348 KiB

stones

#include "bits/stdc++.h"
#define ll long long

using namespace std;

struct STree {
    vector<int> st, lz;
    int sz, n;
    STree(int N): sz(4 * N + 100), n(N) {
        st.assign(sz, 0);
        lz.assign(sz, 0);
    }
    void relax(int v) {
        st[v] += lz[v];
        if (v * 2 < sz)
            lz[v * 2] += lz[v];
        if (v * 2 + 1 < sz)
            lz[v * 2 + 1] += lz[v];
        lz[v] = 0;
    }
    void upd(int lo, int hi, int ix, int v, int k) {
        if (lo > ix) return;
        relax(v);
        if (hi <= ix) {
            lz[v] += k;
            relax(v);
        } else {
            int mi = (lo + hi) / 2;
            upd(lo, mi, ix, v * 2, k);
            upd(mi + 1, hi, ix, v * 2 + 1, k);
            st[v] = min(st[v * 2], st[v * 2 + 1]);
        }
    }
    int qry() {
        relax(1);
        return st[1];
    }
};

int main() {
    int n;
    cin >> n;

    STree le(n), ri(n);

    for (int i = 0; i < n; i ++) {
        int a, b;
        cin >> a >> b;
        if (1 == b) {
            le.upd(1, n, a, 1, -1);
            ri.upd(1, n, a, 1, 1);
        } else {
            le.upd(1, n, a, 1, 1);
            ri.upd(1, n, a, 1, -1);
        }
        int lq = le.qry(), rq = ri.qry();
        if (0 > lq && rq >= 0)
            cout << ">\n";
        else if (0 > rq && lq >= 0)
            cout << "<\n";
        else cout << "?\n";
    }
}

• Subtask 1: 0 / 100