Submission #1247749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247749		makmed1337	Seats (IOI18_seats)	C++20	17 / 100	4094 ms	39720 KiB

seats

#include "seats.h"
#include <algorithm>
#include <vector>

using namespace std;

constexpr int inf = 1e9;
struct Tree {
    struct T {
        int mn = inf, mx = -inf;
        static T from(int x) { return {x, x}; }
        T static combine(T f, T s) { return {min(f.mn, s.mn), max(f.mx, s.mx)}; }
    };

    vector<T> tree;
    void pull(int i) { tree[i] = T::combine(tree[2 * i], tree[2 * i + 1]); }

    void init(vector<int> const &base) {
        int n = base.size();
        tree.resize(4 * n);
        _build(1, 0, n - 1, base);
    }

    void _build(int i, int l, int r, vector<int> const &base) {
        if (l == r) {
            tree[i] = T::from(base[l]);
            return;
        }

        int m = (l + r) / 2;
        _build(2 * i, l, m, base);
        _build(2 * i + 1, m + 1, r, base);
        pull(i);
    }

    T get(int i, int l, int r, int lb, int rb) const {
        if (r < lb || l > rb) {
            return {};
        }

        if (lb <= l && r <= rb) {
            return tree[i];
        }

        int m = (l + r) / 2;
        return T::combine(get(2 * i, l, m, lb, rb), get(2 * i + 1, m + 1, r, lb, rb));
    }

    void update(int i, int l, int r, int pos, int x) {
        if (pos < l || pos > r) {
            return;
        }

        if (l == r) {
            tree[i] = T::from(x);
            return;
        }

        int m = (l + r) / 2;
        update(2 * i, l, m, pos, x);
        update(2 * i + 1, m + 1, r, pos, x);
        pull(i);
    }
};

vector<pair<int, int>> pos;
vector<pair<pair<int, int>, pair<int, int>>> bounds;
Tree rt, ct;
int n, res;

int get_square(pair<pair<int, int>, pair<int, int>> a) {
    auto [r, c] = a;
    return (r.second - r.first + 1) * (c.second - c.first + 1);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    n = H * W;
    pos.resize(n);
    bounds.resize(n);
    res = 0;

    pair<int, int> rr{1e9, -1}, cc{1e9, -1};
    for (int i = 0; i < n; i++) {
        pos[i] = {R[i], C[i]};

        rr.first = min(rr.first, pos[i].first);
        rr.second = max(rr.second, pos[i].first);

        cc.first = min(cc.first, pos[i].second);
        cc.second = max(cc.second, pos[i].second);

        bounds[i] = {rr, cc};

        res += get_square(bounds[i]) == i + 1;
    }

    // rt.init(R);
    // ct.init(C);
}

int swap_seats(int a, int b) {
    if (a > b) {
        swap(a, b);
    }
    swap(pos[a], pos[b]);

    pair<int, int> rr{1e9, -1}, cc{1e9, -1};
    if (a) {
        rr = bounds[a - 1].first;
        cc = bounds[a - 1].second;
    }

    for (int i = a; i < b; i++) {
        res -= get_square(bounds[i]) == i + 1;

        rr.first = min(rr.first, pos[i].first);
        rr.second = max(rr.second, pos[i].first);

        cc.first = min(cc.first, pos[i].second);
        cc.second = max(cc.second, pos[i].second);

        bounds[i] = {rr, cc};

        res += get_square(bounds[i]) == i + 1;
    }

    return res;
    // rt.update(1, 0, n - 1, a, r[a]);
    // rt.update(1, 0, n - 1, b, r[b]);
    //
    // ct.update(1, 0, n - 1, a, c[a]);
    // ct.update(1, 0, n - 1, b, c[b]);
    //
    //
    // int res = 0;
    // int i = 0;
    // while (i < n) {
    //     auto rr = rt.get(1, 0, n - 1, 0, i);
    //     auto cc = ct.get(1, 0, n - 1, 0, i);
    //     int sz = (rr.mx - rr.mn + 1) * (cc.mx - cc.mn + 1);
    //     if (sz == i + 1) {
    //         res++;
    //         ++i;
    //     } else {
    //         i = sz - 1;
    //     }
    // }
    // return res;
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 0 / 20
• Subtask 4: 6 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30