Submission #294160

#	Time	Username	Problem	Language	Result	Execution time	Memory
294160		Saboon	Seats (IOI18_seats)	C++17	5 / 100	4035 ms	48760 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 10;
int n, h, w;
vector<int> r, c;

int MxC[4*maxn], MxR[4*maxn], MnC[4*maxn], MnR[4*maxn];

void change(int id, int L, int R, int idx){
	if (L+1 == R){
		MxR[id] = MnR[id] = r[L];
		MxC[id] = MnC[id] = c[L];
		return;
	}
	int mid = (L + R) >> 1;
	int lc = 2*id+0, rc = 2*id+1;
	if (idx < mid)
		change(lc, L, mid, idx);
	else
		change(rc, mid, R, idx);
	MxC[id] = max(MxC[lc], MxC[rc]);
	MxR[id] = max(MxR[lc], MxR[rc]);
	MnC[id] = min(MnC[lc], MnC[rc]);
	MnR[id] = min(MnR[lc], MnR[rc]);
}

inline pair<int,int> merge(pair<int,int> fi, pair<int,int> se){
	return {min(fi.first,se.first), max(fi.second,se.second)};
}

pair<int,int> getR(int id, int L, int R, int r){
	if (R <= r)
		return {MnR[id],MxR[id]};
	int mid = (L + R) >> 1;
	auto it = getR(2*id+0, L, mid, r);
	if (mid < r)
		it = merge(it,getR(2*id+1,mid,R,r));
	return it;
}

pair<int,int> getC(int id, int L, int R, int r){
	if (R <= r)
		return {MnC[id],MxC[id]};
	int mid = (L + R) >> 1;
	auto it = getC(2*id+0, L, mid, r);
	if (mid < r)
		it = merge(it,getC(2*id+1,mid,R,r));
	return it;
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
	h = H, w = W, r = R, c = C;
	n = h*w;
	for (int i = 0; i < n; i++)
		change(1, 0, n, i);
}

bool isGood(int &r1, int &r2, int &c1, int &c2){
	int Size = (r2-r1+1) * (c2-c1+1);
	auto it = getR(1, 0, n, Size);
	if (it.second > r2){
		r2 = it.second;
		return false;
	}
	if (it.first < r1){
		r1 = it.first;
		return false;
	}
	it = getC(1, 0, n, Size);
	if (it.second > c2){
		c2 = it.second;
		return false;
	}
	if (it.first < c1){
		c1 = it.first;
		return false;
	}
	if (r[Size] < r1)
		r1 = r[Size];
	if (r[Size] > r2)
		r2 = r[Size];
	if (c[Size] < c1)
		c1 = c[Size];
	if (c[Size] > c2)
		c2 = c[Size];
	return true;
}

int swap_seats(int a, int b){
	swap(r[a],r[b]);
	swap(c[a],c[b]);
	change(1, 0, n, a);
	change(1, 0, n, b);
	int r1 = r[0], r2 = r[0], c1 = c[0], c2 = c[0], ret = 0;
	int Size = 1;
	while (Size < n){
		int tmp = isGood(r1, r2, c1, c2);
		ret += tmp;
		Size = (r2-r1+1) * (c2-c1+1);
	}
	ret ++; // h*w 
	return ret;
}

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