Submission #874081

#	Time	Username	Problem	Language	Result	Execution time	Memory
874081		The_Samurai	Weighting stones (IZhO11_stones)	C++17	100 / 100	107 ms	7536 KiB

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 / 100