oj.uz

Submission #523182

# Submission time Handle Problem Language Result Execution time Memory
523182 2022-02-07T07:25:51 Z redstonegamer22 Weighting stones (IZhO11_stones) C++17
0 / 100
 1 ms 336 KB 
#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) {
    if(r < gl || gr < l) return;
    push_lazy(node);

    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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -