Submission #434058

#	Time	Username	Problem	Language	Result	Execution time	Memory
434058		frodakcin	Seats (IOI18_seats)	C++11	11 / 100	4078 ms	102444 KiB

seats

#include "seats.h"
#include <cassert>
#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 H, W, N, ans;
std::vector<int> R, C;

//Subtasks 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;
}

//Subtask 3
struct ST
{
	public:
		std::vector<int> v;
		int S;
		ST(int _S=0): S(_S), v(_S*4, 0) {}
		void init(int _S)
		{
			S=_S;
			v.assign(_S*4, 0);
		}

		void set(int n, int l, int r, int q, int val)
		{
			if(r-l>1)
			{
				int m=l+(r-l)/2;
				if(q<m) set(n<<1, l, m, q, val);
				else set(n<<1|1, m, r, q, val);
				v[n]=std::max(v[n<<1], v[n<<1|1]);
			}
			else v[n]=val;
		}
		void set(int q, int val) {set(1, 0, S, q, val);}

		int qry(int n, int l, int r, int qr)
		{
			if(r <= qr) return v[n];
			if(r-l>1)
			{
				int m=l+(r-l)/2;
				int f=qry(n<<1, l, m, qr);
				if(m<qr) ckmax(f, qry(n<<1|1, m, r, qr));
				return f;
			}
			assert(0);
		}
		int qry(int q) {return qry(1, 0, S, q);}
} mxrst, mnrst, mxcst, mncst;

int st3()
{
	int f=0;
	int n=1;
	for(;n <= N;)
	{
		int sz = (mxrst.qry(n)+mnrst.qry(n))*(mxcst.qry(n)+mncst.qry(n));
		if(sz == n) ++f, ++n;
		else n=sz;
	}
	return f;
}

void give_initial_chart(int _H, int _W, std::vector<int> _R, std::vector<int> _C) {
	H=_H, W=_W;
	R=_R, C=_C;
	N = H*W;
	if(H <= 1000 && W <= 1000)
	{
		mxrst.init(N);
		mnrst.init(N);
		mxcst.init(N);
		mncst.init(N);
		for(int i=0;i<N;++i)
		{
			mxrst.set(i, R[i]+1);
			mnrst.set(i, -R[i]);
			mxcst.set(i, C[i]+1);
			mncst.set(i, -C[i]);
		}
		return;
	}
	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(H <= 1000 && W <= 1000)
	{
		for(int i:{a,b})
		{
			mxrst.set(i, R[i]+1);
			mnrst.set(i, -R[i]);
			mxcst.set(i, C[i]+1);
			mncst.set(i, -C[i]);
		}
		return st3();
	}
	if(b<a) std::swap(a,b);
	return calc(a, b+1);
}

Compilation message (stderr)

seats.cpp: In constructor 'ST::ST(int)':
seats.cpp:39:7: warning: 'ST::S' will be initialized after [-Wreorder]
   39 |   int S;
      |       ^
seats.cpp:38:20: warning:   'std::vector<int> ST::v' [-Wreorder]
   38 |   std::vector<int> v;
      |                    ^
seats.cpp:40:3: warning:   when initialized here [-Wreorder]
   40 |   ST(int _S=0): S(_S), v(_S*4, 0) {}
      |   ^~

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