Submission #743073

#	Time	Username	Problem	Language	Result	Execution time	Memory
743073		piOOE	Sweeping (JOI20_sweeping)	C++17	100 / 100	7172 ms	75840 KiB

sweeping

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int inf = 1e9 + 7;

mt19937 rnd(228);

void ckmax(int &x, int y) {
    if (x < y) {
        x = y;
    }
}

struct Node {
    int prior = 0, sz = 0;
    int x = 0, y = 0, mxy = 0, mny = inf;
    int pushx = -1, pushy = -1;
    int L = 0, R = 0, par = 0;

    Node() = default;
    Node(int prior, int x, int y, int siz) : prior(prior), x(x), y(y), sz(siz), mxy(y), mny(y) {}
};

vector<Node> t{{}};

int create(Node b = Node()) {
    t.emplace_back(b);
    return t.size() - 1;
}

void apply(int p, int pushx, int pushy) {
    if (p == 0) {
        return;
    }
    ckmax(t[p].x, pushx);
    ckmax(t[p].pushx, pushx);
    ckmax(t[p].y, pushy);
    ckmax(t[p].pushy, pushy);
    ckmax(t[p].mxy, t[p].y);
    ckmax(t[p].mny, pushy);
}

void push(int x) {
    for (int p : {t[x].L, t[x].R}) {
        apply(p, t[x].pushx, t[x].pushy);
    }
    t[x].pushx = t[x].pushy = -1;
}

void pull(int x) {
    t[x].sz = 1 + t[t[x].L].sz + t[t[x].R].sz;
    t[x].mxy = max({t[x].y, t[t[x].L].mxy, t[t[x].R].mxy});
    t[x].mny = min({t[x].y, t[t[x].L].mny, t[t[x].R].mny});
    for (int p : {t[x].L, t[x].R}) {
        if (p) {
            t[p].par = x;
        }
    }
}

int merge(int l, int r) {
    t[l].par = t[r].par = 0;
    if (!l || !r) {
        return l ^ r;
    }
    push(l), push(r);
    if (t[l].prior > t[r].prior) {
        t[l].R = merge(t[l].R, r);
        pull(l);
        return l;
    } else {
        t[r].L = merge(l, t[r].L);
        pull(r);
        return r;
    }
}


//key <= k
pair<int, int> split_x(int x, int k) {
    if (!x) {
        return {};
    }
    t[x].par = 0;
    push(x);
    if (t[x].x > k) {
        auto se = split_x(t[x].L, k);
        t[x].L = se.second;
        pull(x);
        return {se.first, x};
    } else {
        auto se = split_x(t[x].R, k);
        t[x].R = se.first;
        pull(x);
        return {x, se.second};
    }
}

int super_merge(int x, int y) {
    t[x].par = t[y].par = 0;
    if (!x || !y) {
        return x ^ y;
    }
    push(x), push(y);
    if (t[x].prior < t[y].prior) {
        swap(x, y);
    }
    auto [l, r] = split_x(y, t[x].x);
    t[x].L = super_merge(t[x].L, l);
    t[x].R = super_merge(t[x].R, r);
    pull(x);
    return x;
}

//left.y <= k
pair<int, int> split_y(int x, int k) {
    t[x].par = 0;
    if (!x || t[x].mxy <= k) {
        return {x, 0};
    } else if (t[x].mny > k) {
        return {0, x};
    }
    push(x);
    auto [ly, lx] = split_y(t[x].L, k);
    auto [ry, rx] = split_y(t[x].R, k);
    if (t[x].y <= k) {
        t[x].L = ly, t[x].R = ry;
        pull(x);
        return {x, merge(lx, rx)};
    } else {
        t[x].L = lx, t[x].R = rx;
        pull(x);
        return {merge(ly, ry), x};
    }
}

pair<int, int> getValue(int x) {
    int px = t[x].x, py = t[x].y;
    while (x > 0) {
        ckmax(px, t[x].pushx);
        ckmax(py, t[x].pushy);
        x = t[x].par;
    }
    return {px, py};
}

void debug_node(int x, string pref = "") {
    if (!x) {
        return;
    }
    pref += "->" + to_string(x);
    debug_node(t[x].L, pref);
    cout << pref << endl;
    debug_node(t[x].R, pref);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;

    vector<int> pos(m + q);

    int root = 0;

    vector<int> X(m), Y(m), ord(m);
    for (int i = 0; i < m; ++i) {
        cin >> X[i] >> Y[i];
    }

    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return X[i] < X[j];
    });

    for (int i : ord) {
        int x = X[i], y = Y[i];
        pos[i] = create(Node(rnd(), x, y, 1));
        root = merge(root, pos[i]);
    }

    for (int qwq = 1; qwq <= q; ++qwq) {
        int T;
        cin >> T;

        if (T == 1) {
            int p;
            cin >> p;
            auto [x, y] = getValue(pos[p - 1]);
            cout << x << " " << y << '\n';
        } else if (T == 2) {
            int H;
            cin >> H;
            auto [l, r] = split_y(root, H);
            apply(l, n - H, 0);
            root = super_merge(l, r);
        } else if (T == 3) {
            int V;
            cin >> V;
            auto [l, r] = split_x(root, V);
            apply(l, 0, n - V);
            root = merge(l, r);
        } else {
            int x, y;
            cin >> x >> y;
            pos[m] = create(Node(rnd(), x, y, 1));
            auto [l, r] = split_x(root, x);
            root = merge(l, merge(pos[m], r));
            m += 1;
        }
    }

    return 0;
}

Compilation message (stderr)

sweeping.cpp: In constructor 'Node::Node(int, int, int, int)':
sweeping.cpp:18:16: warning: 'Node::y' will be initialized after [-Wreorder]
   18 |     int x = 0, y = 0, mxy = 0, mny = inf;
      |                ^
sweeping.cpp:17:20: warning:   'int Node::sz' [-Wreorder]
   17 |     int prior = 0, sz = 0;
      |                    ^~
sweeping.cpp:23:5: warning:   when initialized here [-Wreorder]
   23 |     Node(int prior, int x, int y, int siz) : prior(prior), x(x), y(y), sz(siz), mxy(y), mny(y) {}
      |     ^~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25