Submission #608540

#	Time	Username	Problem	Language	Result	Execution time	Memory
608540		KoD	Seats (IOI18_seats)	C++17	33 / 100	2898 ms	119216 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using std::array;
using std::pair;
using std::vector;

constexpr int inf = std::numeric_limits<int>::max() / 2;
constexpr int dx[] = {0, 1, 0, -1};
constexpr int dy[] = {1, 0, -1, 0};

class range_min {
    int size;
    vector<int> data;

  public:
    range_min() = default;

    explicit range_min(const int n) : size(n), data(2 * n, inf) {}

    void set(int i, const int x) {
        i += size;
        data[i] = x;
        while (i > 1) {
            i >>= 1;
            data[i] = std::min(data[2 * i], data[2 * i + 1]);
        }
    }

    int min() const { return data[1]; }
};

class lazy_segtree {
    static constexpr pair<int, int> unit = {inf, 0};

    int size, logn;
    vector<pair<int, int>> data;
    vector<int> lazy;

    void apply(const int k, const int e) {
        data[k].first += e;
        if (k < size)
            lazy[k] += e;
    }
    void flush(const int k) {
        if (lazy[k] != 0) {
            apply(2 * k, lazy[k]);
            apply(2 * k + 1, lazy[k]);
            lazy[k] = 0;
        }
    }
    void push(const int k) {
        const int lsb = __builtin_ctz(k);
        for (int d = logn; d > lsb; --d)
            flush(k >> d);
    }

    void fetch(const int k) {
        const auto& [ml, cl] = data[2 * k];
        const auto& [mr, cr] = data[2 * k + 1];
        const int m = std::min(ml, mr);
        data[k] = {m, (m == ml ? cl : 0) + (m == mr ? cr : 0)};
    }
    void pull(int k) {
        k >>= __builtin_ctz(k);
        while (k > 1)
            fetch(k >>= 1);
    }

  public:
    lazy_segtree() = default;

    explicit lazy_segtree(const int n) {
        logn = 0;
        while ((1 << logn) < n)
            logn += 1;
        size = 1 << logn;
        data.resize(2 * size, unit);
        lazy.resize(size, 0);
        for (int i = 0; i < n; ++i)
            data[size + i] = {0, 1};
        for (int i = size - 1; i > 0; --i)
            fetch(i);
    }

    void add(int l, int r, const int x) {
        l += size, r += size;
        push(l), push(r);
        const int lc = l, rc = r;
        while (l < r) {
            if (l & 1)
                apply(l++, x);
            if (r & 1)
                apply(--r, x);
            l >>= 1, r >>= 1;
        }
        pull(lc), pull(rc);
    }

    int get() const { return data[1].second; }

    int get(int i) {
        i += size;
        for (int d = logn; d > 0; --d)
            flush(i >> d);
        return data[i].first;
    }
};

int H, W, N;
vector<int> R, C;
vector<vector<int>> grid;
vector<range_min> row, col;
lazy_segtree seg;

bool inside(const int i, const int j) {
    return 0 <= i and i < H and 0 <= j and j < W;
}

int get(const int i, const int j) {
    return inside(i, j) ? grid[i][j] : N;
}

void add(const int a, const int b, const int c) {
    if (a < b)
        seg.add(a, b, c);
}

void update(const int i, const int j, const int c) {
    array<int, 4> a;
    for (int k = 0; k < 4; ++k)
        a[k] = get(i + dx[k], j + dy[k]);
    const int x = get(i, j);
    for (int k = 0; k < 4; ++k) {
        add(a[k], x, c);
        add(std::max(a[k], a[k == 3 ? 0 : k + 1]), x, c);
    }
}

void give_initial_chart(int h, int w, vector<int> r, vector<int> c) {
    H = h, W = w;
    R = r, C = c;
    N = H * W;
    grid = vector(H, vector<int>(W));
    row = vector(H, range_min(W));
    col = vector(W, range_min(H));
    seg = lazy_segtree(N);
    for (int i = 0; i < N; ++i) {
        grid[R[i]][C[i]] = i;
        row[R[i]].set(C[i], i);
        col[C[i]].set(R[i], i);
    }
    for (int i = 0; i < H; ++i)
        seg.add(row[i].min(), N, -2);
    for (int j = 0; j < W; ++j)
        seg.add(col[j].min(), N, -2);
    for (int i = -1; i <= H; ++i)
        for (int j = -1; j <= W; ++j)
            update(i, j, 1);
}

void assign(const int i, const int j, const int x) {
    seg.add(row[i].min(), N, 2);
    seg.add(col[j].min(), N, 2);
    update(i, j, -1);
    for (int k = 0; k < 4; ++k)
        update(i + dx[k], j + dy[k], -1);
    grid[i][j] = x;
    row[i].set(j, x);
    col[j].set(i, x);
    seg.add(row[i].min(), N, -2);
    seg.add(col[j].min(), N, -2);
    update(i, j, 1);
    for (int k = 0; k < 4; ++k)
        update(i + dx[k], j + dy[k], 1);
}

int swap_seats(int a, int b) {
    assign(R[a], C[a], b);
    assign(R[b], C[b], a);
    std::swap(R[a], R[b]);
    std::swap(C[a], C[b]);
    return seg.get();
}

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