Submission #434034

#	Time	Username	Problem	Language	Result	Execution time	Memory
434034		frodakcin	Seats (IOI18_seats)	C++11	17 / 100	4050 ms	55492 KiB

seats

#include "seats.h"
#include <algorithm>

template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}

const int INF = 0x3f3f3f3f;

int N, ans;
std::vector<int> R, C;

//ST 1, 2, 4
std::vector<int> maxr, minr, maxc, minc;

int calc(int u, int v)
{
	for(int i=u;i<v;++i)
		if(i+1 == (maxr[i+1]-minr[i+1])*(maxc[i+1]-minc[i+1]))
			--ans;

	for(int i=u;i<v;++i)
	{
		minr[i+1]=std::min(minr[i], R[i]);
		maxr[i+1]=std::max(maxr[i], R[i]+1);
		minc[i+1]=std::min(minc[i], C[i]);
		maxc[i+1]=std::max(maxc[i], C[i]+1);
		if(i+1 == (maxr[i+1]-minr[i+1])*(maxc[i+1]-minc[i+1]))
			++ans;
	}
	return ans;
}

void give_initial_chart(int H, int W, std::vector<int> _R, std::vector<int> _C) {
	R=_R, C=_C;
	N = H*W;
	maxr.assign(N+1, -1);
	maxc.assign(N+1, -1);
	minr.assign(N+1, INF);
	minc.assign(N+1, INF);
	calc(0, N);
}

int swap_seats(int a, int b) {
	std::swap(R[a], R[b]);
	std::swap(C[a], C[b]);
	if(b<a) std::swap(a,b);
	return calc(a, b+1);
}

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