Submission #1255856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255856		biank	Seats (IOI18_seats)	C++20	100 / 100	1381 ms	99132 KiB

seats

#include <bits/stdc++.h>

using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

using ii = pair<int, int>;
using vi = vector<int>;

#define fst first
#define snd second

#define pb push_back
#define eb emplace_back

const int SZ = 1 << 20;
const int INF = 1e9 + 9;

int mini[2 * SZ], cnt[2 * SZ], lazy[2 * SZ];

void pass(int u) {
    if (u < SZ) {
        lazy[2 * u + 1] += lazy[u];
        lazy[2 * u] += lazy[u];
    }
    mini[u] += lazy[u];
    lazy[u] = 0;
}

void compute(int u) {
    if (mini[2 * u] < mini[2 * u + 1]) {
        mini[u] = mini[2 * u], cnt[u] = cnt[2 * u];
    } else if (mini[2 * u + 1] < mini[2 * u]) {
        mini[u] = mini[2 * u + 1], cnt[u] = cnt[2 * u + 1];
    } else {
        mini[u] = mini[2 * u], cnt[u] = cnt[2 * u] + cnt[2 * u + 1];
    }
}

void update(int s, int e, int v, int l = 0, int r = SZ, int u = 1) {
    pass(u);
    if (e <= l || r <= s) return;
    if (s <= l && r <= e) {
        lazy[u] += v;
        return pass(u);
    }
    int m = (l + r) / 2;
    update(s, e, v, l, m, 2 * u);
    update(s, e, v, m, r, 2 * u + 1);
    compute(u);
}

vector<vi> val;

void change(int i, int j, int delta) {
    vi value = {val[i][j], val[i + 1][j], val[i][j + 1], val[i + 1][j + 1]};
    sort(all(value));
    update(value[0], value[1], delta);
    update(value[2], value[3], delta);
}

vi r, c;

void give_initial_chart(int H, int W, vi R, vi C) {
    r = R, c = C;
    val.assign(H + 2, vi(W + 2, SZ));
    forn(i, H * W) val[R[i] + 1][C[i] + 1] = i;
    forn(i, 2 * SZ) mini[i] = INF, cnt[i] = 0;
    vi delta(SZ + 1, 0);
    forn(i, H + 1) forn(j, W + 1) {
        vi value = {val[i][j], val[i + 1][j], val[i][j + 1], val[i + 1][j + 1]};
        sort(all(value));
        delta[value[0]]++;
        delta[value[1]]--;
        delta[value[2]]++;
        delta[value[3]]--;
    }
    int pref = 0;
    forn(i, H * W) {
        pref += delta[i];
        mini[i + SZ] = pref;
        cnt[i + SZ] = 1;
    }
    dforsn(i, 1, SZ) compute(i);
}

int swap_seats(int a, int b) {
    forn(x, 2) forn(y, 2) {
        change(r[a] + x, c[a] + y, -1);
        change(r[b] + x, c[b] + y, -1);
    }
    swap(r[a], r[b]);
    swap(c[a], c[b]);
    val[r[a] + 1][c[a] + 1] = a;
    val[r[b] + 1][c[b] + 1] = b;
    forn(x, 2) forn(y, 2) {
        change(r[a] + x, c[a] + y, 1);
        change(r[b] + x, c[b] + y, 1);
    }
    assert(mini[1] == 4);
    return cnt[1];
}

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