| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1260511 | anteknne | 자리 배치 (IOI18_seats) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false
const int MAXN = 1000 * 1000 + 17;
pii pos[MAXN];
pii st[4 * MAXN]; //min, ile
int lazy[4 * MAXN];
vector<int> a[MAXN];
int h, w;
void szykuj (int i) {
lazy[i * 2] += lazy[i];
lazy[i * 2 + 1] += lazy[i];
st[i * 2].st += lazy[i];
st[i * 2 + 1].st += lazy[i];
lazy[i] = 0;
}
void buduj (int p, int k, int i) {
if (p == k) {
st[i].nd = 1;
return;
}
int sr = (p + k)/ 2;
buduj(p, sr, i * 2);
buduj(sr + 1, k, i * 2 + 1);
st[i].nd = st[i * 2].nd + st[i * 2 + 1].nd;
}
void aktualizuj (int p, int k, int a, int b, int w, int i) {
if (k < a || p > b) {
return;
}
if (a <= p && k <= b) {
st[i].st += w;
lazy[i] += w;
return;
}
szykuj(i);
int sr = (p + k)/ 2;
aktualizuj(p, sr, a, b, w, i * 2);
aktualizuj(sr + 1, k, a, b, w, i * 2 + 1);
if (st[i * 2].st == st[i * 2 + 1].st) {
st[i].st = st[i * 2].st;
st[i].nd = st[i * 2].nd + st[i * 2 + 1].nd;
} else if (st[i * 2].st < st[i * 2 + 1].st) {
st[i].st = st[i * 2].st;
st[i].nd = st[i * 2].nd;
} else {
st[i].st = st[i * 2 + 1].st;
st[i].nd = st[i * 2 + 1].nd;
}
}
void rob (int i, int j) {
vector<int> v = {a[i][j], a[i - 1][j], a[i][j - 1], a[i - 1][j - 1]};
sort(v.begin(), v.end());
aktualizuj(0, h * w - 1, v[0], v[1] - 1, 1, 1);
//cout << v[0] << " " << v[1] - 1 << "\n";
aktualizuj(0, h * w - 1, v[2], v[3] - 1, 5, 1);
}
void rob2 (int i, int j) {
rob(i, j);
rob(i + 1, j);
rob(i, j + 1);
rob(i + 1, j + 1);
}
void mrob (int i, int j) {
vector<int> v = {a[i][j], a[i - 1][j], a[i][j - 1], a[i - 1][j - 1]};
sort(v.begin(), v.end());
aktualizuj(0, h * w - 1, v[0], v[1] - 1, -1, 1);
//cout << v[0] << " " << v[1] - 1 << "\n";
aktualizuj(0, h * w - 1, v[2], v[3] - 1, -5, 1);
}
void mrob2 (int i, int j) {
mrob(i, j);
mrob(i + 1, j);
mrob(i, j + 1);
mrob(i + 1, j + 1);
}
int main () {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int q;
cin >> h >> w >> q;
for (int i = 0; i <= h + 1; i ++) {
for (int j = 0; j <= w + 1; j ++) {
a[i].pb(h * w);
}
}
for (int i = 0; i < h * w; i ++) {
cin >> pos[i].st >> pos[i].nd;
pos[i].st ++;
pos[i].nd ++;
a[pos[i].st][pos[i].nd] = i;
}
buduj(0, h * w - 1, 1);
for (int i = 1; i <= h + 1; i ++) {
for (int j = 1; j <= w + 1; j ++) {
rob(i, j);
}
}
int x, y;
while (q --) {
cin >> x >> y;
mrob2(pos[x].st, pos[x].nd);
mrob2(pos[y].st, pos[y].nd);
swap(pos[x], pos[y]);
swap(a[pos[x].st][pos[x].nd], a[pos[y].st][pos[y].nd]);
rob2(pos[x].st, pos[x].nd);
rob2(pos[y].st, pos[y].nd);
cout << st[1].nd << "\n";
}
return 0;
}