Submission #874081

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
874081	2023-11-16T08:57:28 Z	The_Samurai	Weighting stones (IZhO11_stones)	C++17	100 / 100	107 ms	7536 KB

stones

// #pragma GCC optimize("Ofast,O3")
// #pragma GCC target("avx,avx2")
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const ll inf = 1e18;

 template<typename T> struct LazySegTree {
    struct Node {
        T mn, mx, lazy;

        Node() {
            // maybe changes
            mn = inf; mx = -inf; // sum - 0, max - (-LLINF), min - LLINF
            lazy = 0;
        }

        Node operator=(const T x) {
            mn = mx = x;
            lazy = 0;
            return *this;
        }

        void merge(const Node &a, const Node &b) {
            mn = min(a.mn, b.mn);
            mx = max(a.mx, b.mx);
        }

        void impact(T v) {
            // maybe changes
            mx += v; mn += v;
            lazy += v;
        }

        void propagate(Node &a, Node &b) {
            // maybe changes
            if (lazy != 0) {
                a.impact(lazy);
                b.impact(lazy);
                lazy = 0;
            }
        }
    };

    vector<Node> tree;
    Node neutral_element;
    int size;

    LazySegTree(int n) {
        init(n);
    }

    void init(int n) {
        size = 1;
        while (size < n) size *= 2;
        Node zeros;
        zeros.mn = zeros.mx = 0;
        tree.assign(2 * size - 1, zeros);
    }


    void set(int l, int r, T v, int x, int lx, int rx) {
        if (l >= rx or lx >= r) return;
        if (l <= lx and rx <= r) {
            tree[x].impact(v);
            return;
        }
        tree[x].propagate(tree[2 * x + 1], tree[2 * x + 2]);
        int mid = (lx + rx) >> 1;
        set(l, r, v, 2 * x + 1, lx, mid);
        set(l, r, v, 2 * x + 2, mid, rx);
        tree[x].merge(tree[2 * x + 1], tree[2 * x + 2]);
    }

    void set(int l, int r, T v) { // [l, r]
        set(l, r + 1, v, 0, 0, size);
    }

    Node get(int l, int r, int x, int lx, int rx) {
        if (l >= rx or lx >= r) return neutral_element;
        if (l <= lx and rx <= r) return tree[x];
        tree[x].propagate(tree[2 * x + 1], tree[2 * x + 2]);
        int mid = (lx + rx) >> 1;
        Node ans;
        ans.merge(get(l, r, 2 * x + 1, lx, mid), get(l, r, 2 * x + 2, mid, rx));
        return ans;
    }

    Node get(int l, int r) { // [l, r]
        return get(l, r + 1, 0, 0, size);
    }
};

void solve() {
    int n;
    cin >> n;
    LazySegTree<ll> sg(n + 1);
    for (int i = 0; i < n; i++) {
        int x, op;
        cin >> x >> op;
        if (op == 1) sg.set(1, x, 1);
        else sg.set(1, x, -1);
        // cout << sg.get(1, n).mn << ' ' << sg.get(1, n).mx << endl;
        if (sg.get(1, n).mx <= 0) cout << '<';
        else if (sg.get(1, n).mn >= 0) cout << '>';
        else cout << '?';
        cout << '\n';
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int q = 1;
    // cin >> q;
    while (q--) {
        solve();
        cout << '\n';
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	2 ms	460 KB	Output is correct
9	Correct	2 ms	348 KB	Output is correct
10	Correct	7 ms	1292 KB	Output is correct
11	Correct	53 ms	3956 KB	Output is correct
12	Correct	107 ms	7252 KB	Output is correct
13	Correct	89 ms	7504 KB	Output is correct
14	Correct	88 ms	7384 KB	Output is correct
15	Correct	95 ms	7388 KB	Output is correct
16	Correct	88 ms	7508 KB	Output is correct
17	Correct	91 ms	7508 KB	Output is correct
18	Correct	88 ms	7536 KB	Output is correct
19	Correct	76 ms	7536 KB	Output is correct
20	Correct	80 ms	7396 KB	Output is correct
21	Correct	93 ms	7504 KB	Output is correct
22	Correct	104 ms	7508 KB	Output is correct
23	Correct	98 ms	7504 KB	Output is correct
24	Correct	94 ms	7508 KB	Output is correct
25	Correct	92 ms	7504 KB	Output is correct