Submission #817568

#	Time	Username	Problem	Language	Result	Execution time	Memory
817568		Dan4Life	Seats (IOI18_seats)	C++17	0 / 100	4077 ms	58940 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
using vi = vector<int>;
const int MX = (int)1e6+10;
vi r, c;
int n, m, ans;
int a[MX];
int rMin[MX*2], rMax[MX*2], cMin[MX*2], cMax[MX*2];
 
void upd(int x, int v, int seg[], bool t, int p=0, int l=0, int r=n*m){
	if(l==r){ seg[p] = v; return; }
	int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
	if(x<=mid) upd(x,v,seg,t,p+1,l,mid);
	else upd(x,v,seg,t,rp,mid+1,r);
	if(t) seg[p] = max(seg[p+1],seg[rp]);
	else seg[p] = min(seg[p+1],seg[rp]);
}
 
int rmq(int i, int j, int seg[], bool t, int p=0, int l=0, int r=n*m){
	if(i>r or j<l or i>j) return t?0:MX;
	if(i<=l and r<=j) return seg[p];
	int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
	int le = t?0:MX; int ri = le;
	if(i<=mid) le = rmq(i,j,seg,t,p+1,l,mid);
	if(j>mid) ri = rmq(i,j,seg,t,rp,mid+1,r);
	if(t) return max(le,ri);
	return min(le,ri);
}
 
void give_initial_chart(int H, int W, vi R, vi C) {
	n = H, m = W; r = R; c = C;
	fill(rMin,rMin+MX*2,n*m);
	fill(cMin,cMin+MX*2,n*m);
	for(int i = 0; i < n*m; i++){
		upd(i,r[i],rMin,0); upd(i,r[i],rMax,1); upd(i,c[i],cMin,0); upd(i,c[i],cMax,1);
		a[i] = ((i+1)==((rmq(0,i,rMax,1)-rmq(0,i,rMin,0)+1)*((rmq(0,i,cMax,1)-rmq(0,i,cMin,0)+1))));
		ans+=a[i];
	}
}
 
bool bad(int le, int ri, int up, int dow, int x){
	if(rmq(0,x,rMin,0)<up) return 1;
	if(rmq(0,x,rMax,1)>dow) return 1;
	if(rmq(0,x,cMin,0)<le) return 1;
	if(rmq(0,x,cMax,1)>ri) return 1;
	return 0;
}

int swap_seats(int x, int y) {
	if(n*m==1) return 1;
	if(x>y) swap(x,y);
	swap(r[x],r[y]); swap(c[x],c[y]);
	int i = x; upd(i,r[i],rMin,0); upd(i,r[i],rMax,1); upd(i,c[i],cMin,0); upd(i,c[i],cMax,1);
	i = y; upd(i,r[i],rMin,0); upd(i,r[i],rMax,1); upd(i,c[i],cMin,0); upd(i,c[i],cMax,1);
	int le = c[0], ri = c[0], up = r[0], dow = r[0], ans = 0;
	while(1){
		int area = (ri-le+1)*(dow-up+1);
		if(area==n*m) break;
		int K;
		{
			int l = 0, r = n*m-1;
			while(l<r){
				int mid = (l+r+1)/2;
				if(bad(le,ri,up,dow,mid)) r=mid;
				else l=mid+1;
			}
			K = l;
		}
		if(K==area) ans++;
		
		int R = r[K], C = c[K];
		ri=max(ri,R); le=min(le,R);
		dow=max(dow,C); up=min(up,C);
		if(!bad(le,ri,up,dow,K)) break;
	}
	return ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30