Submission #1290998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290998		k1r1t0	Seats (IOI18_seats)	C++20	100 / 100	3252 ms	106520 KiB

seats

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>

#define lv (v + 1)
#define rv (v + 2 * (mid - l + 1))

using namespace std;
using ll = long long;

const int N = 1100000;

int h, w, n, r[N], c[N], vec[N];

int get(int i, int j) {
    if (i < 1 || j < 1 || i > h || j > w)
        return n + 1;
    i--; j--;
    return vec[i * w + j];
}

int vv[2 * N][5], uu[2 * N][5];

void merge(int v, int l, int r) {
    for (int i = 0; i < 5; i++)
        vv[v][i] = 0;
    if (uu[v][4] > 0)
        return;
    int sum = 0;
    for (int i = 0; i < 4; i++)
        sum += uu[v][i];
    if (sum > 4)
        return;
    if (l == r) {
        vv[v][sum] = 1;
        return;
    }
    int mid = (l + r) / 2;
    for (int i = 0; i + sum < 5; i++)
        vv[v][i + sum] = vv[lv][i] + vv[rv][i];
}

void build(int v, int l, int r) {
    if (l != r) {
        int mid = (l + r) / 2;
        build(lv, l, mid);
        build(rv, mid + 1, r);
    }
    merge(v, l, r);
}

void upd(int v, int l, int r, int ql, int qr, int m, int k) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        uu[v][k] += m;
        merge(v, l, r);
        return;
    }
    int mid = (l + r) / 2;
    upd(lv, l, mid, ql, qr, m, k);
    upd(rv, mid + 1, r, ql, qr, m, k);
    merge(v, l, r);
}

void upd(int i, int j, int m) {
    int a = get(i, j);
    int b = get(i, j + 1);
    int c = get(i + 1, j);
    int d = get(i + 1, j + 1);
    vector<int> v = {a, b, c, d};
    sort(begin(v), end(v));
    int l = v[0], r = v[1] - 1;
    if (l <= r) {
        if (v[0] == a) {upd(1, 1, n, l, r, m, 0);}
        if (v[0] == b) {upd(1, 1, n, l, r, m, 1);}
        if (v[0] == c) {upd(1, 1, n, l, r, m, 2);}
        if (v[0] == d) {upd(1, 1, n, l, r, m, 3);}
    }
    l = v[2], r = v[3] - 1;
    if (l <= r) {
        if (v[3] == a) {upd(1, 1, n, l, r, m, 4);}
    }
}

int ans() {
    return vv[1][4];
}

void give_initial_chart(int _H, int _W, vector<int> _R, vector<int> _C) {
    h = _H;
    w = _W;
    n = h * w;
    for (int i = 1; i <= n; i++)
        vec[(r[i] = _R[i - 1]) * w + (c[i] = _C[i - 1])] = i;
    build(1, 1, n);
    for (int i = 0; i <= h; i++)
    for (int j = 0; j <= w; j++)
        upd(i, j, 1);
}

int swap_seats(int a, int b) {
    a++; b++;
    vector<array<int, 2>> pos;
    for (int i = -1; i <= 0; i++)
    for (int j = -1; j <= 0; j++) {
        pos.push_back({r[a] + i + 1, c[a] + j + 1});
        pos.push_back({r[b] + i + 1, c[b] + j + 1});
    }
    sort(begin(pos), end(pos));
    pos.erase(unique(begin(pos), end(pos)), end(pos));
    for (auto [x, y] : pos)
        upd(x, y, -1);
    swap(r[a], r[b]);
    swap(c[a], c[b]);
    swap(vec[r[a] * w + c[a]], vec[r[b] * w + c[b]]);
    for (auto [x, y] : pos)
        upd(x, y, 1);
    return ans();
}









































#ifdef LOCAL

namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
  int H = read_int();
  int W = read_int();
  int Q = read_int();
  std::vector<int> R(H * W), C(H * W);
  for (int i = 0; i < H * W; ++i) {
    R[i] = read_int();
    C[i] = read_int();
  }
  std::vector<int> A(Q), B(Q);
  for (int j = 0; j < Q; ++j) {
    A[j] = read_int();
    B[j] = read_int();
  }

  give_initial_chart(H, W, R, C);
  for (int j = 0; j < Q; ++j) {
    int answer = swap_seats(A[j], B[j]);
    printf("%d\n", answer);
  }
  return 0;
}

#endif

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