| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 112791 | imaxblue | 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.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define vi vector<int>
#define vpii vector<pii>
#define vp3i vector<p3i>
#define vpll vector<pll>
#define vp3l vector<p3l>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() ((rand() << 14)+rand())
#define scan(X) do{while((X=getchar())<'0'); for(X-='0'; '0'<=(_=getchar()); X=(X<<3)+(X<<1)+_-'0');}while(0)
char _;
#define pi 3.14159265358979323846
int h, w, n, r[1000005], c[1000005];
int lo[8000005], hi[8000005];
int lo2[8000005], hi2[8000005];
int gl, gr, v, v2, ans2;
void add(int L, int R, int N){
if (L > gr || R <gl) return;
if (gl <= L && R<=gr){
//cout << L << ' ' << R << ' ' << v << ' ' << v2 << endl;
lo[N]=hi[N] = v;
lo2[N]=hi2[N] =v2;
return;
}
add(lseg); add(rseg);
lo[N] = min(lo[N*2+1], lo[N*2+2]);
hi[N] = max(hi[N*2+1], hi[N*2+2]);
lo2[N] = min(lo2[N*2+1], lo2[N*2+2]);
hi2[N] = max(hi2[N*2+1], hi2[N*2+2]);
}
void turn(int N, int X, int Y){
v = X; v2 = Y; gl = gr = N;
add(0, n-1, 0);
}
pair<pii, pii> query(int L, int R, int N){
if (L > gr || R < gl) return mp(mp(1<<30, 0), mp((1<<30), 0));
if (gl <= L && R <= gr){
//cout << gl << ' ' << gr << ' ' << L << ' ' << R << ' ' << lo[N] << ' ' << hi[N] << ' ' << lo2[N] << ' ' << hi2[N] << endl;
return mp(mp(lo[N], hi[N]), mp(lo2[N], hi2[N]));
}
pair<pii, pii> tmp = query(lseg), tmp2 = query(rseg);
tmp.x.x = min(tmp.x.x, tmp2.x.x);
tmp.x.y = max(tmp.x.y, tmp2.x.y);
tmp.y.x = min(tmp.y.x, tmp2.y.x);
tmp.y.y = max(tmp.y.y, tmp2.y.y);
//cout << "*" << tmp.y.y << ' ' << tmp2.y.y << endl;
return tmp;
}
pair<pii, pii> get(int N){
gl = 0; gr = N;
return query(0, n-1, 0);
}
bool good[1000005];
pair<pii, pii> tmp2[1000005];
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
h = H;
w = W;
n = h*w;
flood(lo);
flood(lo2);
fox(l, n){
r[l] = R[l];
c[l] = C[l];
turn(l, R[l], C[l]);
}
int t=1;
pair<pii, pii> tmp = mp(mp(1<<30, 0), mp(1<<30, 0));
while(t <= n){
tmp.x.x = min(tmp.x.x, r[t-1]);
tmp.x.y = max(tmp.x.y, r[t-1]);
tmp.y.x = min(tmp.y.x, c[t-1]);
tmp.y.y = max(tmp.y.y, c[t-1]);
tmp2[t] = tmp;
if((tmp.x.y - tmp.x.x+1)*(tmp.y.y-tmp.y.x+1) == t){
//cout << t << endl;
ans2++;
good[t] = 1;
}
//cout << tmp.x.x << ' ' << tmp.x.y << ' ' << tmp.y.x << ' ' << tmp.y.y << endl;
//cout << t << endl
t++;
}
}
int swap_seats(int a, int b){
int x = r[a], y = c[a];
turn(a, r[b], c[b]);
turn(b, x, y);
r[a] = r[b]; c[a] = c[b];
r[b] = x; c[b] = y;
int t = 1, ans = 0;
pair<pii, pii> tmp = mp(mp(1<<30, 0), mp(1<<30, 0));
if (h <=1000 && w <= 1000){
while(t <= n){
tmp = get(t-1);
while((tmp.x.y - tmp.x.x+1)*(tmp.y.y-tmp.y.x+1) > t){
//cout << t << endl;
t = (tmp.x.y - tmp.x.x+1)*(tmp.y.y-tmp.y.x+1);
tmp = get(t-1);
}
//cout << tmp.x.x << ' ' << tmp.x.y << ' ' << tmp.y.x << ' ' << tmp.y.y << endl;
//cout << t << endl;
ans++;
t++;
}
return ans;
}
if (a > b) swap(a, b);
if (a > 0) tmp = tmp2[a-1];
ans2=0;
pair<pii, pii> tmp = mp(mp(1<<30, 0), mp(1<<30, 0));
while(t <= n){
tmp.x.x = min(tmp.x.x, r[t-1]);
tmp.x.y = max(tmp.x.y, r[t-1]);
tmp.y.x = min(tmp.y.x, c[t-1]);
tmp.y.y = max(tmp.y.y, c[t-1]);
tmp2[t] = tmp;
if((tmp.x.y - tmp.x.x+1)*(tmp.y.y-tmp.y.x+1) == t){
//cout << t << endl;
ans2++;
good[t] = 1;
}
//cout << tmp.x.x << ' ' << tmp.x.y << ' ' << tmp.y.x << ' ' << tmp.y.y << endl;
//cout << t << endl
t++;
}
return ans2;
for (int l = 1; l <= n; ++l){
//ans2 -= good[l];
tmp.x.x = min(tmp.x.x, r[l-1]);
tmp.x.y = max(tmp.x.y, r[l-1]);
tmp.y.x = min(tmp.y.x, c[l-1]);
tmp.y.y = max(tmp.y.y, c[l-1]);
good[l] = ((tmp.x.y - tmp.x.x+1)*(tmp.y.y-tmp.y.x+1) == l);
tmp2[l] = tmp;
ans2 += good[l];
}
return ans2;
}
/*
int32_t main(){
int H, W, x, q, a, b;
vector<int> R, C;
cin >> H >> W;
fox(l, H*W){
cin >> x;
R.pb(x);
}
fox(l, H*W){
cin >> x;
C.pb(x);
}
give_initial_chart(H, W, R, C);
cin >> q;
fox(l, q){
cin >> a >> b;
cout << swap_seats(a, b) << endl;
}
return 0;
}*/
/*
2 3
0 1 1 0 0 1
0 0 1 1 2 2
100
0 5
0 5
3 4
*/