Submission #1074784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074784		coolboy19521	Weighting stones (IZhO11_stones)	C++17	100 / 100	286 ms	7796 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) {
        relax(v);
        if (lo > ix) return;
        if (hi <= ix) {
            lz[v] += k;
            relax(v);
            //cout << "updd: " << lo << ' ' << hi << ' ' << st[v] << '\n';
        } 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]);
            //cout << "upd: " << lo << ' ' << hi << ' ' << st[v * 2] << ' ' << st[v * 2 + 1] << '\n';
        }
    }
    int qry(int lo, int hi, int ql, int qr, int v) {
        relax(v);
        if (lo > qr || ql > hi) return 2e5;
        if (ql <= lo && hi <= qr) return st[v];
        int mi = (lo + hi) / 2;
        int lq = qry(lo, mi, ql, qr, v * 2);
        int rq = qry(mi + 1, hi, ql, qr, v * 2 + 1);
        return min(lq, rq);
    }
};

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(1, n, 1, n, 1), rq = ri.qry(1, n, 1, n, 1);
        //cout << "hi: " << lq << ' ' << rq << ' ' << le.qry(1, n, 5, 5, 1) << '\n';
        if (0 > lq && rq >= 0)
            cout << ">\n";
        else if (0 > rq && lq >= 0)
            cout << "<\n";
        else cout << "?\n";
    }
}

• Subtask 1: 100 / 100