Submission #413779

#	Time	Username	Problem	Language	Result	Execution time	Memory
413779		timmyfeng	Seats (IOI18_seats)	C++17	70 / 100	4080 ms	103236 KiB

seats

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1000000;
 
array<int, 2> pos[N];
vector<int> seats[N];
int n, m;

struct segtree {
    int mini, count, lazy;
} mini[4 * N];
 
void apply(int u, int x) {
    mini[u].lazy += x, mini[u].mini += x;
}
 
void push(int u) {
    if (mini[u].lazy != 0) {
        apply(2 * u, mini[u].lazy);
        apply(2 * u + 1, mini[u].lazy);
        mini[u].lazy = 0;
    }
}
 
void pull(int u) {
    mini[u].mini = min(mini[2 * u].mini, mini[2 * u + 1].mini);
    mini[u].count = 0;
    if (mini[2 * u].mini == mini[u].mini) {
        mini[u].count += mini[2 * u].count;
    }
    if (mini[2 * u + 1].mini == mini[u].mini) {
        mini[u].count += mini[2 * u + 1].count;
    }
}
 
void build(int u, int l, int r) {
    mini[u].count = r - l + 1;
    if (l < r) {
        int m = (l + r) / 2;
        build(2 * u, l, m);
        build(2 * u + 1, m + 1, r);
    }
}
 
void update(int u, int a, int b, int x, int l, int r) {
    if (a > b || b < l || r < a) {
        return;
    } else if (a <= l && r <= b) {
        apply(u, x);
    } else {
        push(u);
        int m = (l + r) / 2;
        update(2 * u, a, b, x, l, m);
        update(2 * u + 1, a, b, x, m + 1, r);
        pull(u);
    }
}
 
void update(int i, int j, int x) {
    vector<int> in;
    for (auto ki : {-1, 0}) {
        for (auto kj : {-1, 0}) {
            if (0 <= i + ki && i + ki < n && 0 <= j + kj && j + kj < m) {
                in.push_back(seats[i + ki][j + kj]);
            } else {
                in.push_back(n * m);
            }
        }
    }
    sort(in.begin(), in.end());
 
    update(1, in[0], in[1] - 1, x, 0, n * m - 1);
    update(1, in[2], in[3] - 1, 4 * 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]};
    }
 
    build(1, 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[1].count;
}

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