Submission #817195

#	Time	Username	Problem	Language	Result	Execution time	Memory
817195		Dan4Life	Seats (IOI18_seats)	C++17	5 / 100	4061 ms	59024 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];
	}
}

int swap_seats(int x, int y) {
	if(x>y) swap(x,y);
	swap(r[x],r[y]); swap(c[x],c[y]);
	for(int i = x; i <= y; i++){
		ans-=a[i];
		if(i==x or 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);
		}
		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];
	} 
	return ans;
}

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