# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1211626 | mar | Seats (IOI18_seats) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int r[MAXN], c[MAXN];
int mnr[MAXN], mxr[MAXN], mnc[MAXN], mxc[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int h, w;
cin >> h >> w;
int n = h * w;
for (int i = 0; i < n; ++i) cin >> r[i];
for (int i = 0; i < n; ++i) cin >> c[i];
int ans = 0;
int cur_mnr = r[0], cur_mxr = r[0], cur_mnc = c[0], cur_mxc = c[0];
for (int i = 0; i < n; ++i) {
cur_mnr = min(cur_mnr, r[i]);
cur_mxr = max(cur_mxr, r[i]);
cur_mnc = min(cur_mnc, c[i]);
cur_mxc = max(cur_mxc, c[i]);
mnr[i] = cur_mnr;
mxr[i] = cur_mxr;
mnc[i] = cur_mnc;
mxc[i] = cur_mxc;
if ((i + 1) == (mxr[i] - mnr[i] + 1) * (mxc[i] - mnc[i] + 1)) {
++ans;
}
}
int q;
cin >> q;
while (q--) {
int a, b;
cin >> a >> b;
swap(r[a], r[b]);
swap(c[a], c[b]);
mnr[0] = mxr[0] = r[0];
mnc[0] = mxc[0] = c[0];
for (int i = 1; i < n; ++i) {
mnr[i] = min(mnr[i - 1], r[i]);
mxr[i] = max(mxr[i - 1], r[i]);
mnc[i] = min(mnc[i - 1], c[i]);
mxc[i] = max(mxc[i - 1], c[i]);
}
ans = 0;
for (int i = 0; i < n; ++i) {
int area = (mxr[i] - mnr[i] + 1) * (mxc[i] - mnc[i] + 1);
if ((i + 1) == area) ++ans;
}
cout << ans << '\n';
}
return 0;
}