| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 793056 | 1bin | 자리 배치 (IOI18_seats) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#include "seats.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int b = 1 << 20;
int n, lazy[b * 2], W, v[b * 3], pfx[b];
int seg[b * 2][2];
vector<int> Y, X;
void upd_lazy(int ix, int l, int r){
if(!lazy[ix]) return;
seg[ix][0] += lazy[ix];
if(l ^ r){
lazy[ix * 2] += lazy[ix];
lazy[ix * 2 + 1] += lazy[ix];
}
lazy[ix] = 0;
return;
}
void upd(int ix, int nl, int nr, int l, int r, int v){
upd_lazy(ix, nl, nr);
if(nl > r || nr < l) return;
if(nl >= l && nr <= r){
lazy[ix] += v;
upd_lazy(ix, nl, nr);
return;
}
int m = (nl + nr) / 2;
upd(ix * 2, nl, m, l, r, v);
upd(ix * 2 + 1, m + 1, nr, l, r, v);
seg[ix][0] = min(seg[ix * 2][0], seg[ix * 2 + 1][0]);
seg[ix][1] = (seg[ix * 2][0] == seg[ix][0] ? seg[ix * 2][1] : 0) + (seg[ix * 2 + 1][0] == seg[ix][0] ? seg[ix * 2 + 1][1] : 0);
return;
}
void calc(int ix, int p){
vector<int> t;
for(int i = -1; i <= 0; i++)
for(int j = -1; j <= 0; j++)
t.emplace_back(v[ix + i * (W + 2) + j]);
sort(all(t));
upd(1, 0, b - 1, t[0], t[1] - 1, p);
upd(1, 0, b - 1, t[2], t[3] - 1, p);
return;
}
void give_initial_chart(int H, int W_, vector<int> R, vector<int> C) {
Y = R; X = C; W = W_;
n = H * W;
for(int i = 0; i <= (H + 2) * (W + 2); i++) v[i] = n;
for(int i = 0; i < n; i++) v[++Y[i] * (W + 2) + ++X[i]] = i;
for(int i = b; i < b * 2; i++) seg[i][0] = b;
for(int y = 1; y <= H + 1; y++)
for(int x = 1; x <= W + 1; x++) {
vector<int> t;
for(int i = -1; i <= 0; i++)
for(int j = -1; j <= 0; j++)
t.emplace_back(v[(y + i) * (W + 2) + x + j]);
sort(all(t));
pfx[t[0]]++;
pfx[t[1]]--;
pfx[t[2]]++;
pfx[t[3]]--;
}
int cur = 0;
for(int i = 0; i < n; i++){
cur += pfx[i];
seg[b + i][0] = cur;
seg[b + i][1] = 1;
}
for(int i = b - 1; i; i--){
seg[i][0] = min(seg[i * 2][0], seg[i * 2 + 1][0]);
seg[i][1] = (seg[i * 2][0] == seg[i][0] ? seg[i * 2][1] : 0) + (seg[i * 2 + 1][0] == seg[i][0] ? seg[i * 2 + 1][1] : 0);
}
return;
}
int swap_seats(int i1, int i2) {
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++){
calc((Y[i1] + i) * (W + 2) + X[i1] + j, -1);
calc((Y[i2] + i) * (W + 2) + X[i2] + j, -1);
}
swap(Y[i1], Y[i2]);
swap(X[i1], X[i2]);
swap(v[Y[i1] * (W + 2) + X[i1]], v[Y[i2] * (W + 2) + X[i2]]);
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++){
calc((Y[i1] + i) * (W + 2) + X[i1] + j, 1);
calc((Y[i2] + i) * (W + 2) + X[i2] + j, 1);
}
if(seg[1][0] == 4) return seg[1][1];
return 0;
}
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m, q, a, b;
cin >> n >> m >> q;
vector<int> h(n * m), w(n * m);
for(int i = 0; i < n * m; i++) cin >> h[i] >> w[i];
give_initial_chart(n, m, h, w);
cin >> q;
while(q--){
cin >> a >> b;
cout << swap_seats(a, b) << '\n';
}
return 0;
}