Submission #523189

#	Time	Username	Problem	Language	Result	Execution time	Memory
523189		redstonegamer22	Weighting stones (IZhO11_stones)	C++17	100 / 100	239 ms	3704 KiB

stones

#include <bits/stdc++.h>

using namespace std;

const int offset = (1 << 17);
const int NMAX = 100000 + 7;

int lazy[2 * offset], maxs[2 * offset], mins[2 * offset];

void push_lazy(int node) {
    maxs[node] += lazy[node];
    mins[node] += lazy[node];

    if(node < offset) {
        lazy[2 * node] += lazy[node];
        lazy[2 * node + 1] += lazy[node];
    }

    lazy[node] = 0;
}

void update(int node, int l, int r, int gl, int gr, int upd) {
    push_lazy(node);
    if(r < gl || gr < l) return;

    if(gl <= l && r <= gr) {
        lazy[node] += upd;
        push_lazy(node);
        return;
    }

    int mid = (l + r) / 2;
    update(2 * node, l, mid, gl, gr, upd);
    update(2 * node + 1, mid + 1, r, gl, gr, upd);

    maxs[node] = max(maxs[2 * node], maxs[2 * node + 1]);
    mins[node] = min(mins[2 * node], mins[2 * node + 1]);

    return;
}

int main()
{
    assert(offset > NMAX);

    int n; cin >> n;

    for(int i = 0; i < n; i++) {
        int x, s; cin >> x >> s;
        if(s == 1) update(1, 0, offset - 1, 0, x, +1);
        else update(1, 0, offset - 1, 0, x, -1);

#ifdef LOCAL
        cerr << '\t' << maxs[1] << " " << mins[1] << endl;
#endif // LOCAL

        if(maxs[1] > 0 && mins[1] < 0) cout << '?' << endl;
        else if(maxs[1] > 0) cout << '>' << endl;
        else cout << '<' << endl;
    }

    return 0;
}

• Subtask 1: 100 / 100