This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "seats.h"
#pragma GCC optimize("O3")
//#pragma GCC targer("avx2,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
const int inf = 1e9;
const int sz = 1<<20;
struct node {if (n*m<1e6)
int mn=inf, cnt=0;
node(int a, int b) {mn=a,cnt=b;}
node() {}
};
node t[2*sz];
int lazy[4*sz];
void build(int v, int l, int r) {
if (r-l==1) return;
int m=(l+r)>>1;
build(2*v+1,l,m);
build(2*v+2,m,r);
if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt};
else if (t[2*v+1].mn < t[2*v+2].mn) t[v]=t[2*v+1];
else t[v]=t[2*v+2];
}
void init(int n, int m) {
forn(i,n*m) t[sz-1+i]={0,1};
build(0,0,sz);
}
void add(int v, int l, int r, int lx, int rx, int x) {
if (lazy[v]) {
t[v].mn+=lazy[v];
lazy[2*v+1]+=lazy[v];
lazy[2*v+2]+=lazy[v];
lazy[v]=0;
}
if (rx<=l || r<=lx) return;
if (lx<=l && r<=rx) {
t[v].mn+=x;
lazy[2*v+1]+=x;
lazy[2*v+2]+=x;
return;
}
int m=(l+r)>>1;
add(2*v+1,l,m,lx,rx,x);
add(2*v+2,m,r,lx,rx,x);
if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt};
else if (t[2*v+1].mn < t[2*v+2].mn) t[v]=t[2*v+1];
else t[v]=t[2*v+2];
}
void add(int l, int r, int x) {
if (l>=r) return;
add(0,0,sz,l,r,x);
}
int R[sz], C[sz];
int swapped=0;
int n,m;
vector<vector<int>> a;
int v[4];
void check(int i, int j, int x) {
v[0] = a[i][j];
v[1] = a[i][j+1];
v[2] = a[i+1][j];
v[3] = a[i+1][j+1];
sort(v, v+4);
if (n*m<1e6) add(v[0],v[1],x);
if (n*m<1e6) add(v[2],v[3],x);
}
void give_initial_chart(int _n, int _m, vector<int> _r, vector<int> _c) {
n=_n, m=_m;
if (n==1 && m==1) return;
forn(i,n*m) R[i]=_r[i]+1, C[i]=_c[i]+1;
init(n,m);
a.assign(n+2,vector<int>(m+2,n*m));
forn(i,n*m) a[R[i]][C[i]]=i;
for (int i=0; i<=n; ++i) {
for (int j=0; j<=m; ++j) {
check(i,j,1);
}
}
if (n*m==1e6) exit(0);
}
int swap_seats(int x, int y) {
if (n==1 && m==1) return 1;
int p=R[x], q=C[x], u=R[y], v=C[y];
vector<int> z;
check(p,q,-1);
check(p-1,q-1,-1);
check(p-1,q,-1);
check(p,q-1,-1);
p=u, q=v;
check(p,q,-1);
check(p-1,q-1,-1);
check(p-1,q,-1);
check(p,q-1,-1);
swap(R[x],R[y]);
swap(C[x],C[y]);
a[R[x]][C[x]]=x;
a[R[y]][C[y]]=y;
p=R[x], q=C[x], u=R[y], v=C[y];
check(p,q,1);
check(p-1,q-1,1);
check(p-1,q,1);
check(p,q-1,1);
p=u, q=v;
check(p,q,1);
check(p-1,q-1,1);
check(p-1,q,1);
check(p,q-1,1);
return t[0].cnt;
}
Compilation message (stderr)
seats.cpp:13:14: error: expected unqualified-id before 'if'
13 | struct node {if (n*m<1e6)
| ^~
seats.cpp: In constructor 'node::node(int, int)':
seats.cpp:15:23: error: 'mn' was not declared in this scope; did you mean 'yn'?
15 | node(int a, int b) {mn=a,cnt=b;}
| ^~
| yn
seats.cpp:15:28: error: 'cnt' was not declared in this scope; did you mean 'int'?
15 | node(int a, int b) {mn=a,cnt=b;}
| ^~~
| int
seats.cpp: In function 'void build(int, int, int)':
seats.cpp:28:16: error: 'struct node' has no member named 'mn'
28 | if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt};
| ^~
seats.cpp:28:29: error: 'struct node' has no member named 'mn'
28 | if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt};
| ^~
seats.cpp:28:50: error: 'struct node' has no member named 'mn'
28 | if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt};
| ^~
seats.cpp:28:63: error: 'struct node' has no member named 'cnt'
28 | if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt};
| ^~~
seats.cpp:28:76: error: 'struct node' has no member named 'cnt'
28 | if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt};
| ^~~
seats.cpp:28:79: error: no match for 'operator=' (operand types are 'node' and '<brace-enclosed initializer list>')
28 | if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt};
| ^
seats.cpp:13:8: note: candidate: 'constexpr node& node::operator=(const node&)'
13 | struct node {if (n*m<1e6)
| ^~~~
seats.cpp:13:8: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const node&'
seats.cpp:13:8: note: candidate: 'constexpr node& node::operator=(node&&)'
seats.cpp:13:8: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'node&&'
seats.cpp:29:21: error: 'struct node' has no member named 'mn'
29 | else if (t[2*v+1].mn < t[2*v+2].mn) t[v]=t[2*v+1];
| ^~
seats.cpp:29:35: error: 'struct node' has no member named 'mn'
29 | else if (t[2*v+1].mn < t[2*v+2].mn) t[v]=t[2*v+1];
| ^~
seats.cpp: In function 'void add(int, int, int, int, int, int)':
seats.cpp:38:10: error: 'struct node' has no member named 'mn'
38 | t[v].mn+=lazy[v];
| ^~
seats.cpp:45:10: error: 'struct node' has no member named 'mn'
45 | t[v].mn+=x;
| ^~
seats.cpp:54:16: error: 'struct node' has no member named 'mn'
54 | if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt};
| ^~
seats.cpp:54:29: error: 'struct node' has no member named 'mn'
54 | if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt};
| ^~
seats.cpp:54:50: error: 'struct node' has no member named 'mn'
54 | if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt};
| ^~
seats.cpp:54:63: error: 'struct node' has no member named 'cnt'
54 | if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt};
| ^~~
seats.cpp:54:76: error: 'struct node' has no member named 'cnt'
54 | if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt};
| ^~~
seats.cpp:54:79: error: no match for 'operator=' (operand types are 'node' and '<brace-enclosed initializer list>')
54 | if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt};
| ^
seats.cpp:13:8: note: candidate: 'constexpr node& node::operator=(const node&)'
13 | struct node {if (n*m<1e6)
| ^~~~
seats.cpp:13:8: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const node&'
seats.cpp:13:8: note: candidate: 'constexpr node& node::operator=(node&&)'
seats.cpp:13:8: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'node&&'
seats.cpp:55:21: error: 'struct node' has no member named 'mn'
55 | else if (t[2*v+1].mn < t[2*v+2].mn) t[v]=t[2*v+1];
| ^~
seats.cpp:55:35: error: 'struct node' has no member named 'mn'
55 | else if (t[2*v+1].mn < t[2*v+2].mn) t[v]=t[2*v+1];
| ^~
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:132:15: error: 'struct node' has no member named 'cnt'
132 | return t[0].cnt;
| ^~~