제출 #1291007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291007		k1r1t0	자리 배치 (IOI18_seats)	C++17	100 / 100	2156 ms	98824 KiB

seats

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

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];

void merget(int v) {
    for (int i = 0; i < 5; i++)
        vv[v][i] = 0;
    if (uu[v] > 4)
        return;
    if (v >= n) {
        vv[v][uu[v]] = 1;
        return;
    }
    for (int i = 0; i + uu[v] < 5; i++)
        vv[v][i + uu[v]] = vv[v * 2 + 0][i] + vv[v * 2 + 1][i];
}

void pusht(int v) {
    while (v > 1) {
        v /= 2;
        merget(v);
    }
}

void buildt() {
    for (int i = n + n - 1; i >= 1; i--)
        merget(i);
}

void updt(int l, int r, int k) {
    l += n - 1; r += n;
    int l0 = l, r0 = r;
    for (; l < r; l /= 2, r /= 2) {
        if (l & 1) {uu[l] += k; merget(l); l++;}
        if (r & 1) {r--; uu[r] += k; merget(r);}
    }
    pusht(l0);
    pusht(r0);
}

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

vector<array<int, 3>> pp;

void resolve() {
    sort(begin(pp), end(pp));
    int x = -1, y = -1, w = -1;
    for (auto [a, b, d] : pp) {
        if (a != x || b != y) {
            if (x != -1 && w != 0)
                updt(x, y, w);
            x = a, y = b, w = d;
        } else w += d;
    }
    if (x != -1 && w != 0)
        updt(x, y, w);
    pp.clear();
}

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)
        pp.push_back({l, r, m});
    l = v[2], r = v[3] - 1;
    if (l <= r)
        pp.push_back({l, r, 5 * m});
}

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;
    buildt();
    for (int i = 0; i <= h; i++)
    for (int j = 0; j <= w; j++)
        upd(i, j, 1);
    resolve();
}

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);
    resolve();
    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