| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1294219 | kyanhdang | Seats (IOI18_seats) | C++17 | 0 ms | 0 KiB |
// kyanhdang was here!
#include <bits/stdc++.h>
#define boostcode ios_base::sync_with_stdio(0); cin.tie(0);
#define openf freopen("seats.inp", "r", stdin); freopen("seats.out", "w", stdout);
#define fi first
#define se second
#define pb(x) push_back(x)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
// NOTE BEFORE READING THE CODE:
// - Values on the table are numbered 1, 2, 3,..., H*W instead of 0, 1, 2,..., H*W-1!
// - This code is suitable to submit on both problems that do/don't require int main()!
const int INF = 1e6 + 1;
int curSubtask; // Which subtask is the test in
int h, w, q;
int SZ;
vector<int> row;
vector<int> col;
/// Segment tree:
struct Border {
int mnr, mxr, mnc, mxc;
Border() {}
Border(int mnr, int mxr/*?(╯°□°）╯︵ ┻━┻ mistyped mxnr*/, int mnc, int mxc) : mnr(mnr), mxr(mxr), mnc(mnc), mxc(mxc) {}
int calSize() {
return (mxr - mnr + 1)*(mxc - mnc + 1);
}
void debug() { // Only for debug:))
cout << mnr << ' ' << mxr << ' ' << mnc << ' ' << mxc;
}
} seg[4000002];
Border combine(const Border &a, const Border &b) {
return Border(min(a.mnr, b.mnr), max(a.mxr, b.mxr),
min(a.mnc, b.mnc), max(a.mxc, b.mxc));
}
void build(int id, int l, int r) {
if (l == r) {
seg[id] = Border(row[l], row[l], col[l], col[l]);
return;
}
int mid = (l + r)>>1;
build(id<<1, l, mid);
build(id<<1 | 1, mid+1, r);
seg[id] = combine(seg[id<<1], seg[id<<1 | 1]);
}
void update(int id, int l, int r, int pos, const Border &val) {
if (pos<l || pos>r) return;
if (l == r) {
seg[id] = val;
return;
}
int mid = (l + r)>>1;
update(id<<1, l, mid, pos, val);
update(id<<1 | 1, mid+1, r, pos, val);
seg[id] = combine(seg[id<<1], seg[id<<1 | 1]);
}
Border query(int id, int l, int r, int u, int v) {
if (r<u || v<l) return Border(INF, -INF, INF, -INF);
if (u<=l && r<=v) {
return seg[id];
}
int mid = (l + r)>>1;
return combine(query(id<<1, l, mid, u, v),
query(id<<1 | 1, mid+1, r, u, v));
}
/// SUBTASK 1+2:
int sub12() {
Border cur = Border(INF, -INF, INF, -INF);
int res = 0;
for (int i = 1; i <= SZ; i++) {
int r = row[i];
int c = col[i];
cur = combine(cur, Border(r, r, c, c));
int sz = cur.calSize();
if (sz == i) res++;
}
return res;
}
/// SUBTASK 3:
int sub3(int a, int b) {
update(1, 1, SZ, a, Border(row[a], row[a], col[a], col[a]));
update(1, 1, SZ, b, Border(row[b], row[b], col[b], col[b]));
Border cur = Border(INF, -INF, INF, -INF);
int res = 0;
for (int i = 1; i <= SZ; i++) {
int r = row[i];
int c = col[i];
cur = combine(cur, Border(r, r, c, c));
int sz = cur.calSize();
while (i<=SZ && i<sz) {
r = row[sz];
c = col[sz];
// cout << i << " --> " << sz << " : "; cur.debug(); cout << '\n';
cur = combine(cur, query(1, 1, SZ, i+1, sz));
// cout << i << " --> " << sz << " : "; cur.debug(); cout << '\n';
i = sz;
sz = cur.calSize();
}
res++;
// cout << i << " : " << sz << " ( "; cur.debug(); cout << " ) " << res << '\n';
}
return res;
}
/// SUBTASK 4:
// Observation: If swap between a and b, the minimum/maximum
// row/column and res will only change between a and b-1.
// ==> We can precalculate minr, maxr, minc, maxc, res for each value i from 1 -> SZ,
// then for each query (a, b), we re-calculate them for value i from a -> b-1
// and returns preres[a-1] + sufres[b] + res (for a -> b-1)
// with preres[a-1] gives res for value i from 1 -> a-1,
// sufres[b] gives res for value i from b -> SZ.
// Time complexity: O(H*W + Q*|a-b|) <= O(H*W + Q*10000) (<= 5e7 + 1e6)
/// Fenwick tree (to calculate pre[i] in subtask 4):
int bit[1000002];
bool valid[1000002]; // Checks if sequence 1, 2,..., i forms a valid rectangle
void update(int pos, int val) {
if ((val==1 && valid[pos]) || (val==-1 && !valid[pos])) return;
if (val == -1) valid[pos] = false;
else valid[pos] = true;
for (; pos <= SZ; pos += (pos&-pos)) {
bit[pos] += val;
}
}
int query(int pos) {
int res = 0;
for (; pos; pos -= (pos&-pos)) {
res += bit[pos];
}
return res;
}
int query(int l, int r) {
return query(r) - query(l-1);
}
Border pre[1000002];
void sub4init() { // Sub 4 initialization
Border cur = Border(INF, -INF, INF, -INF);
pre[0] = cur;
// Calculates preres[i] and pre[i]:
for (int i = 1; i <= SZ; i++) {
int r = row[i];
int c = col[i];
cur = combine(cur, Border(r, r, c, c));
int sz = cur.calSize();
if (sz == i) update(i, 1);
else update(i, -1);
pre[i] = cur;
}
// for (int i = 1; i <= SZ; i++) {
// cout << i << " : "; pre[i].debug(); cout << " | " << query(i) << '\n';
// }
}
int sub4(int a, int b) {
int res = query(1, a-1);
Border cur = pre[a-1];
for (int i = a; i < b; i++) {
int r = row[i];
int c = col[i];
cur = combine(cur, Border(r, r, c, c));
int sz = cur.calSize();
// Updates i-th node in BIT and pre[i] for next queries
if (sz == i) {
res++;
update(i, 1);
} else update(i, -1);
pre[i] = cur;
}
// cout << "Swap " << a << ' ' << b << "!\n";
// for (int i = 1; i <= SZ; i++) {
// cout << i << " : "; pre[i].debug(); cout << " | " << query(i) << '\n';
// }
res = res + query(b, SZ); // Equivalent to res = preres[a-1] + res(just calculated above) + suf[b]
return res;
}
/// Processing queries:
int swap_seats(int a, int b) {
a++;
b++;
if (a > b) swap(a, b);
swap(row[a], row[b]);
swap(col[a], col[b]);
if (curSubtask == 12) return sub12();
if (curSubtask == 3) return sub3(a, b);
// if (curSubtask == 4) return sub4();
return sub4(a, b);
}
void initSubtaskes() { // Initialize subtaskes:
// if ((ll)h*w*q <= 5e7) {
if (h*w<=10000 && q<=5000) {
curSubtask = 12;
return;
}
if (h<=1000 && w<=1000 && q<=5000) {
curSubtask = 3;
build(1, 1, SZ); // sub 3 initialization
return;
}
// sub 4 initialization:
curSubtask = 4;
sub4init();
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h = H;
w = W;
row = R;
col = C;
// Make row[] and col[] start with index 1:
row.insert(row.begin(), -1);
col.insert(col.begin(), -1);
SZ = h*w;
initSubtaskes();
}
int main() {
boostcode;
openf;
cin >> h >> w >> q;
SZ = h*w;
// Make row[] and col[] start with index 1:
row.pb(-1);
col.pb(-1);
for (int i = 0; i < SZ; i++) {
int r, c;
cin >> r >> c;
row.pb(r);
col.pb(c);
}
initSubtaskes();
// Perform queries:
for (int o = 1; o <= q; o++) {
int a, b;
cin >> a >> b;
cout << swap_seats(a, b) << '\n';
}
return 0;
}
/* TESTS:
Test 1:
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5
-->
3
4
Test 2:
1 5 3
0 0
0 1
0 2
0 3
0 4
0 1
0 3
4 0
-->
5
3
2
Test 3:
5 2 2
2 1
0 0
1 1
4 0
3 1
4 1
3 0
2 0
1 0
0 1
4 3
8 5
-->
2
2
Test 4:
-->
*/