제출 #413769

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
413769		timmyfeng	자리 배치 (IOI18_seats)	C++17	33 / 100	3282 ms	162216 KiB

seats

#include <bits/stdc++.h>
using namespace std;

const int N = 1000000;

struct segtree {
    segtree *left, *right;
    int mini, count, lazy;

    void apply(int x) {
        lazy += x, mini += x;
    }

    void push() {
        if (lazy != 0) {
            left->apply(lazy);
            right->apply(lazy);
            lazy = 0;
        }
    }

    void pull() {
        mini = min(left->mini, right->mini);
        count = 0;
        if (left->mini == mini) {
            count += left->count;
        }
        if (right->mini == mini) {
            count += right->count;
        }
    }

    segtree(int l, int r) {
        lazy = 0;
        if (l == r) {
            mini = 0, count = 1;
        } else {
            int m = (l + r) / 2;
            left = new segtree(l, m);
            right = new segtree(m + 1, r);
            pull();
        }
    }

    void update(int a, int b, int x, int l, int r) {
        if (b < l || r < a) {
            return;
        } else if (a <= l && r <= b) {
            apply(x);
        } else {
            push();
            int m = (l + r) / 2;
            left->update(a, b, x, l, m);
            right->update(a, b, x, m + 1, r);
            pull();
        }
    }
};

array<int, 2> pos[N];
vector<int> seats[N];
segtree *mini;
int n, m;

void update(int i, int j, int x) {
    int mini1 = n * m, mini2 = n * m;
    for (auto ki : {-1, 0}) {
        for (auto kj : {-1, 0}) {
            if (0 <= i + ki && i + ki < n) {
                if (0 <= j + kj && j + kj < m) {
                    if (seats[i + ki][j + kj] < mini1) {
                        mini2 = mini1, mini1 = seats[i + ki][j + kj];
                    } else {
                        mini2 = min(mini2, seats[i + ki][j + kj]);
                    }
                }
            }
        }
    }
    mini->update(mini1, mini2 - 1, x, 0, n * m - 1);
}

void give_initial_chart(int n, int m, vector<int> r, vector<int> c) {
    ::n = n, ::m = m;
    fill(seats, seats + n, vector<int>(m));
    for (int i = 0; i < n * m; ++i) {
        seats[r[i]][c[i]] = i;
        pos[i] = {r[i], c[i]};
    }

    mini = new segtree(0, n * m - 1);
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            update(i, j, 1);
        }
    }
}

int swap_seats(int a, int b) {
    vector<array<int, 2>> cells;
    for (auto k : {a, b}) {
        auto [i, j] = pos[k];
        for (auto ki : {0, 1}) {
            for (auto kj : {0, 1}) {
                cells.push_back({i + ki, j + kj});
            }
        }
    }

    sort(cells.begin(), cells.end());
    cells.erase(unique(cells.begin(), cells.end()), cells.end());

    for (auto [i, j] : cells) {
        update(i, j, -1);
    }

    swap(seats[pos[a][0]][pos[a][1]], seats[pos[b][0]][pos[b][1]]);
    swap(pos[a], pos[b]);

    for (auto [i, j] : cells) {
        update(i, j, 1);
    }

    return mini->count;
}

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