제출 #195685

#제출 시각아이디문제언어결과실행 시간메모리
195685Anai자리 배치 (IOI18_seats)C++14
0 / 100
4054 ms48692 KiB
#include <bits/stdc++.h> #ifndef HOME #include "seats.h" #endif #define x first #define y second using namespace std; 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; prop(nod); 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; } double tot; static void baga(int idx, int qt = 1) { clock_t st = clock(); vector<pii> nidx; if (idx == a || f[idx]) return; f[idx]++; 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 = 1 * qt; update(1, 0, a); tot+= 1.0 * (clock() - st) / CLOCKS_PER_SEC; } static void scoate(int idx) { baga(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); 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 = 1, qr = a - 1; return 1 + query(1, 0, a).y; } #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); } cerr << tot << endl; return 0; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...