Submission #131227

#	Time	Username	Problem	Language	Result	Execution time	Memory
131227		bogdan10bos	Seats (IOI18_seats)	C++14	20 / 100	2045 ms	90872 KiB

seats

/// simba :(
#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

int N, M, K;
vector<int> X, Y;
vector< vector<int> > A;

class SegmentTree
{
public:
	int N;
	int sti, dri, val;
	vector<int> aint, add, cnt;

	void B(int nod, int st, int dr)
	{
		aint[nod] = add[nod] = 0, cnt[nod] = dr - st + 1;
		if(st == dr)	return;
		B(nod * 2, st, st + (dr - st) / 2);
		B(nod * 2 + 1, st + (dr - st) / 2 + 1, dr);
	}

	void U(int nod, int st, int dr)
	{
		if(sti <= st && dr <= dri)
		{
			aint[nod] += val;
			add[nod] += val;
			return;
		}

		int mij = st + (dr - st) / 2;
		if(add[nod])
		{
			aint[nod * 2] += add[nod];
			aint[nod * 2 + 1] += add[nod];
			add[nod * 2] += add[nod];
			add[nod * 2 + 1] += add[nod];
			add[nod] = 0;
		}

		if(sti <= mij)	U(nod * 2, st, mij);
		if(mij < dri)	U(nod * 2 + 1, mij + 1, dr);

		aint[nod] = min(aint[nod * 2], aint[nod * 2 + 1]);
		cnt[nod] = 0;
		if(aint[nod] == aint[nod * 2])	cnt[nod] += cnt[nod * 2];
		if(aint[nod] == aint[nod * 2 + 1])	cnt[nod] += cnt[nod * 2 + 1];
	}

	void build(int _N)
	{
		N = _N;
		aint.resize(4 * N), add.resize(4 * N), cnt.resize(4 * N);
		B(1, 0, N - 1);
	}

	void update(int st, int dr, int v)
	{
		if(st > dr)	return;
		sti = st, dri = dr, val = v;
		U(1, 0, N - 1);
	}

	int query()
	{
		return cnt[1];
	}
}aint;

int a(int x, int y)
{
	if(x < 0 || y < 0 || x >= N || y >= M)	return K;
	return A[x][y];
}

void makeBlack(int x, int y, int add)
{
	if(x < 0 || y < 0 || x >= N || y >= M)	return;
	int t = min(a(x - 1, y), a(x, y - 1));
	aint.update(a(x, y), t - 1, add);
}

void makeWhite(int x, int y, int add)
{
	if(x < 0 || y < 0 || x >= N || y >= M)	return;

	vector<int> t;
	t.push_back(a(x - 1, y));
	t.push_back(a(x + 1, y));
	t.push_back(a(x, y - 1));
	t.push_back(a(x, y + 1));
	sort(t.begin(), t.end());

	int tt = t[1];

	aint.update(tt, a(x, y) - 1, add);
}

void solveCell(int x, int y, int add)
{
	makeBlack(x, y, add);
	makeBlack(x + 1, y, add);
	makeBlack(x, y + 1, add);

	makeWhite(x, y, add);
	makeWhite(x - 1, y, add);
	makeWhite(x + 1, y, add);
	makeWhite(x, y - 1, add);
	makeWhite(x, y + 1, add);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
	N = H, M = W;
	K = N * M;
	X = R, Y = C;
	A.resize(N);
	for(int i = 0; i < N; i++)	A[i].resize(M);

	for(int i = 0; i < K; i++)
		A[ X[i] ][ Y[i] ] = i;
	aint.build(K);

	for(int i = 0; i < K; i++)
	{
		makeBlack(X[i], Y[i], 1);
		makeWhite(X[i], Y[i], 1);
	}
}

int swap_seats(int a, int b)
{
	solveCell(X[a], Y[a], -1);
	solveCell(X[b], Y[b], -1);

	swap(X[a], X[b]);
	swap(Y[a], Y[b]);
	A[ X[a] ][ Y[a] ] = a;
	A[ X[b] ][ Y[b] ] = b;

	solveCell(X[a], Y[a], 1);
	solveCell(X[b], Y[b], 1);

	return aint.query();
}

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