| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 738226 | myrcella | Seats (IOI18_seats) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
//#include "seats.h"
const int maxn = 2e6+10;
pair<pii,int> tree[maxn*4];
pii add[maxn*4];
int grid[maxn];
int n;
int val[maxn];
pii pos[maxn];
int h,w;
void update(int c,int cl,int cr,int l,int r,int val1,int val2) {
if (l<=cl and cr<=r) {
tree[c].fi.fi += val1;
tree[c].fi.se += val2;
add[c].fi += val1;
add[c].se += val2;
return;
}
if (add[c]!=MP(0,0)) {
tree[c<<1].fi.fi += add[c].fi;
tree[c<<1].fi.se += add[c].se;
add[c<<1].fi += add[c].fi;
add[c<<1].se += add[c].se;
tree[c<<1|1].fi.fi += add[c].fi;
tree[c<<1|1].fi.se += add[c].se;
add[c<<1|1].fi += add[c].fi;
add[c<<1|1].se += add[c].se;
add[c] = {0,0};
}
int mid=cl+cr>>1;
if (l<=mid) update(c<<1,cl,mid,l,r,val1,val2);
if (r>mid) update(c<<1|1,mid+1,cr,l,r,val1,val2);
if (tree[c<<1].fi==tree[c<<1|1].fi) tree[c] = {tree[c<<1].fi,tree[c<<1].se+tree[c<<1|1].se};
else tree[c] = min(tree[c<<1],tree[c<<1|1]);
}
void update(int x,int y,int v) {
int tm[4] = {val[x*w+y],val[x*w+y+1],val[(x+1)*w+y],val[(x+1)*w+y+1]};
sort(tm,tm+4);
if (tm[0]<tm[1]) update(1,0,n-1,tm[0],tm[1]-1,v,0);
if (tm[2]<tm[3]) update(1,0,n-1,tm[2],tm[3]-1,0,v);
}
void init(int c,int cl,int cr) {
tree[c] = {{0,0},cr-cl+1};
add[c] = {0,0};
if (cl==cr) return;
int mid=cl+cr>>1;
init(c<<1,cl,mid);
init(c<<1|1,mid+1,cr);
return;
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H*W;
h = H+1,w=W+1;
rep(i,0,maxn) val[i] = n;
rep(i,0,n) {
R[i]++;
C[i]++;
val[R[i]*w+C[i]] = i;
pos[i] = {R[i],C[i]};
}
init(1,0,n-1);
rep(i,0,h)
rep(j,0,w) update(i,j,1);
}
int swap_seats(int a, int b) {
update(pos[a].fi,pos[a].se,-1);update(pos[a].fi-1,pos[a].se,-1);update(pos[a].fi,pos[a].se-1,-1);update(pos[a].fi-1,pos[a].se-1,-1);
update(pos[b].fi,pos[b].se,-1);update(pos[b].fi-1,pos[b].se,-1);update(pos[b].fi,pos[b].se-1,-1);update(pos[b].fi-1,pos[b].se-1,-1);
swap(pos[a],pos[b]);
swap(val[pos[a].fi*w+pos[a].se],val[pos[b].fi*w+pos[b].se]);
update(pos[a].fi,pos[a].se, 1);update(pos[a].fi-1,pos[a].se, 1);update(pos[a].fi,pos[a].se-1, 1);update(pos[a].fi-1,pos[a].se-1, 1);
update(pos[b].fi,pos[b].se, 1);update(pos[b].fi-1,pos[b].se, 1);update(pos[b].fi,pos[b].se-1, 1);update(pos[b].fi-1,pos[b].se-1, 1);
// assert(tree[1].fi==MP(4,0));
return tree[1].se;
}
int main() {
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);
}
return 0;
}