Submission #1109775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109775		Kirill22	Weighting stones (IZhO11_stones)	C++17	100 / 100	73 ms	7668 KiB

stones

#include "bits/stdc++.h"

using namespace std;

struct tree {
    vector<int> t, d;

    tree(int n) {
        t.resize(4 * n);
        d.resize(4 * n);
    }

    void push(int v, int l, int r) {
        t[v] += d[v];
        if (l + 1 != r) {
            d[v * 2 + 1] += d[v];
            d[v * 2 + 2] += d[v];
        }
        d[v] = 0;
    }

    void update(int v, int l, int r, int l1, int r1, int x) {
        push(v, l, r);
        if (l1 >= r || l >= r1) {
            return;
        }
        if (l1 <= l && r <= r1) {
            d[v] = x;
            push(v, l, r);
            return;
        }
        int m = (l + r) / 2;
        update(v * 2 + 1, l, m, l1, r1, x);
        update(v * 2 + 2, m, r, l1, r1, x);
        t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
    }

    int get(int n) {
        push(0, 0, n);
        return t[0];
    }
};

void solve() {
    int n;
    cin >> n;
    tree t1(n), t2(n);
    for (int it = 0; it < n; it++) {
        int i, x;
        cin >> i >> x;
        if (x == 1) {
            t1.update(0, 0, n, 0, i, 1);
            t2.update(0, 0, n, 0, i, -1);
        } else {
            t2.update(0, 0, n, 0, i, 1);
            t1.update(0, 0, n, 0, i, -1);
        }
        int l = t1.get(n) >= 0;
        int r = t2.get(n) >= 0;
//        cout << t1.get(n) << " " << t2.get(n) << endl;
        if (!l && !r) {
            cout << "?\n";
        } else if (l) {
            cout << ">\n";
        } else {
            cout << "<\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

• Subtask 1: 100 / 100