Submission #131233

#	Time	Username	Problem	Language	Result	Execution time	Memory
131233		bogdan10bos	Seats (IOI18_seats)	C++14	100 / 100	3434 ms	141664 KiB

seats

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

using namespace std;

typedef pair<int, int> pii;

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);
	}
}

const int cx[] = {0, -1, 1, 0, 0};
const int cy[] = {0, 0, 0, -1, 1};


int swap_seats(int a, int b)
{
	vector<pii> cells;
	for(int i = 0; i < 5; i++)	cells.push_back({X[a] + cx[i], Y[a] + cy[i]});
	for(int i = 0; i < 5; i++)	cells.push_back({X[b] + cx[i], Y[b] + cy[i]});
	sort(cells.begin(), cells.end());
	cells.resize(unique(cells.begin(), cells.end()) - cells.begin());

	for(auto p: cells)
	{
		makeBlack(p.first, p.second, -1);
		makeWhite(p.first, p.second, -1);
	}

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

	for(auto p: cells)
	{
		makeBlack(p.first, p.second, 1);
		makeWhite(p.first, p.second, 1);
	}

	return aint.query();
}

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