Submission #195700

#	Time	Username	Problem	Language	Result	Execution time	Memory
195700		Anai	Seats (IOI18_seats)	C++14	100 / 100	3712 ms	100984 KiB

seats

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#ifndef HOME
    #include "seats.h"
#endif
 
#define x first
#define y second
using namespace std;

namespace {
using pii = pair<int, int>;
 
const int A = 1e6 + 5;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
 
struct Nod {
    int min, cnt, lazy;
};
 
int f[A];
 
vector<vector<int>> mx;
vector<int> row, col;
int n, m, a;
 
int ql, qr, qval;
 
Nod pom[A * 4];
 
 
static void prop(int nod) {
    pom[2 * nod + 1].lazy+= pom[nod].lazy;
    pom[2 * nod].lazy+= pom[nod].lazy;
    pom[nod].min+= pom[nod].lazy;
    pom[nod].lazy = 0;
}
 
static void update(int nod, int st, int dr) {
    if (qr < ql)
        return;
    if (ql <= st && dr <= qr) {
        pom[nod].lazy+= qval;
        return;
    }
    int mid = (st + dr) / 2;
    if (ql <= mid)
        update(2 * nod, st, mid);
    if (mid < qr)
        update(2 * nod + 1, mid + 1, dr);
    pom[nod].min = min(pom[2 * nod].min + pom[2 * nod].lazy, pom[2 * nod + 1].min + pom[2 * nod + 1].lazy);
    pom[nod].cnt = (pom[nod].min == pom[2 * nod].min + pom[2 * nod].lazy ? pom[2 * nod].cnt : 0);
    pom[nod].cnt+= (pom[nod].min == pom[2 * nod + 1].min + pom[2 * nod + 1].lazy ? pom[2 * nod + 1].cnt : 0);
}
 
static pii query(int nod, int st, int dr) {
    if (ql <= st && dr <= qr)
        return pii(pom[nod].min + pom[nod].lazy, pom[nod].cnt);
    int mid = (st + dr) / 2;
    pii ans = {1e9, 1e9};
 
    prop(nod);
    if (ql <= mid)
        ans = query(2 * nod, st, mid);
    if (mid < qr) {
        pii ret = query(2 * nod + 1, mid + 1, dr);
        if (ret.x < ans.x)
            ans = ret;
        else if (ret.x == ans.x)
            ans.y+= ret.y;
    }
 
    return ans;
}
 
static void act(int idx, int qt = 1) {
    static vector<pii> nidx;
    nidx.clear();

    int x = row[idx], y = col[idx];
    for (int dir = 0; dir < 4; ++dir) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        int val = mx[nx][ny];
 
        nidx.emplace_back(val, dir);
    }
 
    sort(begin(nidx), end(nidx));
 
    if (nidx[1].x < idx) {
        ql = nidx[1].x;
        qr = idx - 1;
        qval = 100 * qt;
        update(1, 0, a);
    }
 
    ql = idx;
    qr = nidx[0].x - 1;
    qval = 10 * qt;
    update(1, 0, a);
 
    ql = max(idx, nidx[0].x);
    qr = nidx[1].x - 1;
    qval = 2 * qt;
    update(1, 0, a);
 
    if (nidx[0].y % 2 == nidx[1].y % 2)
        return;
 
    ql = max(idx, nidx[1].x);
    qr = nidx[2].x - 1;
    qval = qt;
    update(1, 0, a);
}
 
static void baga(int idx) {
    if (idx == a || f[idx])
        return;
    f[idx]++;
    act(idx, 1);
}

static void scoate(int idx) {
    if (idx == a || f[idx] == 0)
        return;
    f[idx]--;
    act(idx, -1);
}
 
static void meh(int nod, int st, int dr) {
    if (st == dr) {
        pom[nod].cnt = 1;
        return;
    }
    int mid = (st + dr) / 2;
    meh(2 * nod, st, mid);
    meh(2 * nod + 1, mid + 1, dr);
    pom[nod].cnt = dr - st + 1;
}
};
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    swap(row, R);
    swap(col, C);
    n = H;
    m = W;
    a = n * m;
 
    mx = vector<vector<int>>(n + 5, vector<int>(m + 5));
    for (int i = 0; i < a; ++i)
        mx[++row[i]][++col[i]] = i;
 
    for (int i = 0; i <= n + 1; ++i)
        mx[i][0] = mx[i][m + 1] = a;
    for (int j = 0; j <= m + 1; ++j)
        mx[0][j] = mx[n + 1][j] = a;
 
    meh(1, 0, a);

    ql = qr = 0;
    qval = 1000;
    update(1, 0, a);
    ql = qr = a;
    qval = 1000;
    update(1, 0, a);

    for (int i = 0; i < a; ++i)
        baga(i);
}
 
int swap_seats(int u, int v) {
    static int call = 0; ++call;
    int xu = row[u], yu = col[u];
    int xv = row[v], yv = col[v];
 
 
    scoate(u);
    scoate(v);
    for (int dir = 0; dir < 4; ++dir) {
        int nx = xu + dx[dir];
        int ny = yu + dy[dir];
        scoate(mx[nx][ny]);
    }
        
    for (int dir = 0; dir < 4; ++dir) {
        int nx = xv + dx[dir];
        int ny = yv + dy[dir];
        scoate(mx[nx][ny]);
    }
 
    swap(mx[xu][yu], mx[xv][yv]);
    swap(col[u], col[v]);
    swap(row[u], row[v]);
 
    baga(u);
    baga(v);
    for (int dir = 0; dir < 4; ++dir) {
        int nx = xu + dx[dir];
        int ny = yu + dy[dir];
        baga(mx[nx][ny]);
    }
 
    for (int dir = 0; dir < 4; ++dir) {
        int nx = xv + dx[dir];
        int ny = yv + dy[dir];
        baga(mx[nx][ny]);
    }
 
    ql = 0, qr = a;
    return 1 + pom[1].cnt;
}
 
#ifdef HOME
 
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() {
  freopen("seats.in", "r", stdin);
  freopen("seats.out", "w", stdout);
 
  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