Submission #333647

#	Time	Username	Problem	Language	Result	Execution time	Memory
333647		apostoldaniel854	Weighting stones (IZhO11_stones)	C++14	100 / 100	75 ms	6124 KiB

stones

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

struct SegTree {
    int n;
    vector <int> mx;
    vector <int> mn;
    vector <int> lazy;
    SegTree (int n) {
        this->n = n;
        mx.resize (1 + 4 * n);
        mn.resize (1 + 4 * n);
        lazy.resize (1 + 4 * n);
    }
    void push (int node) {
        int l = node * 2, r = node * 2 + 1;
        mn[l] += lazy[node];
        mx[l] += lazy[node];
        mn[r] += lazy[node];
        mx[r] += lazy[node];
        lazy[l] += lazy[node];
        lazy[r] += lazy[node];
        lazy[node] = 0;
    }
    void update (int node, int lb, int rb, int x, int y, int val) {
        if (x <= lb && rb <= y) {
            mn[node] += val;
            mx[node] += val;
            lazy[node] += val;
            return;
        }
        int mid = (lb + rb) / 2, lNode = node * 2, rNode = node * 2 + 1;
        push (node);
        if (x <= mid)
            update (lNode, lb, mid, x, y, val);
        if (mid + 1 <= y)
            update (rNode, mid + 1, rb, x, y, val);
        mn[node] = min (mn[lNode], mn[rNode]);
        mx[node] = max (mx[lNode], mx[rNode]);
    }
    char query () { /// 1 means >, -1 means <, and 0 means ?
        if (mn[1] >= 0)
            return '>';
        if (mx[1] <= 0)
            return '<';
        return '?';
    }
};

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    int n;
    cin >> n;
    SegTree seg (n);
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        seg.update (1, 1, n, 1, x, (y == 1) ? 1 : -1);
        cout << seg.query () << "\n";
    }
    return 0;
}

• Subtask 1: 100 / 100