Submission #598322

#	Time	Username	Problem	Language	Result	Execution time	Memory
598322		jairRS	Seats (IOI18_seats)	C++17	11 / 100	4077 ms	39480 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

ll h, w;
vector<vector<ll>> grid, prefixGrid;
vector<pii> pos;

bool outOfBounds(pii coords)
{
	int i = coords.first, j = coords.second;
	return i < 0 || i >= h || j < 0 || j >= w;
}

void calcPrefix()
{
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
		{
			pii above = {i - 1, j};
			pii before = {i, j - 1};
			pii upLeft = {i - 1, j - 1};

			ll res = grid[i][j];
			if (!outOfBounds(above))
				res += prefixGrid[above.first][above.second];
			if (!outOfBounds(before))
				res += prefixGrid[before.first][before.second];
			if (!outOfBounds(upLeft))
				res -= prefixGrid[upLeft.first][upLeft.second];
			prefixGrid[i][j] = res;
		}
}

ll getArea(pii tL, pii bR)
{
	return (bR.first - tL.first + 1) * (bR.second - tL.second + 1);
}

ll getRectangleSum(pii topLeftCorner, pii bottomRightCorner)
{
	pii before = {bottomRightCorner.first, topLeftCorner.second - 1};
	pii above = {topLeftCorner.first - 1, bottomRightCorner.second};
	pii upLeft = {topLeftCorner.first - 1, topLeftCorner.second - 1};

	ll res = prefixGrid[bottomRightCorner.first][bottomRightCorner.second];
	if (!outOfBounds(above))
		res -= prefixGrid[above.first][above.second];
	if (!outOfBounds(before))
		res -= prefixGrid[before.first][before.second];
	if (!outOfBounds(upLeft))
		res += prefixGrid[upLeft.first][upLeft.second];
	return res;
}

ll checkBeauty()
{
	ll res = 0;
	int top = 0;
	pair<ll, ll> prevTL = {-1, -1}, prevBR = {-1, -1};
	pair<ll, ll> topLeft = pos[0], bottomRight = pos[0];
	do
	{
		ll area = getArea(topLeft, bottomRight);
		bool isPretty = getRectangleSum(topLeft, bottomRight) == area * (area - 1) / 2;
		top++;
		res += isPretty && (topLeft != prevTL || bottomRight != prevBR);

		prevTL = topLeft;
		prevBR = bottomRight;
		pii posNext = pos[top];
		topLeft.first = min(topLeft.first, (ll)posNext.first);
		topLeft.second = min(topLeft.second, (ll)posNext.second);
		bottomRight.first = max(bottomRight.first, (ll)posNext.first);
		bottomRight.second = max(bottomRight.second, (ll)posNext.second);
	} while (top < h * w);

	return res;
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
	h = H, w = W;
	grid = prefixGrid = vector<vector<ll>>(H, vector<ll>(W));
	pos = vector<pair<int, int>>(H * W);
	for (int i = 0; i < H * W; i++)
	{
		grid[R[i]][C[i]] = i;
		pos[i] = {R[i], C[i]};
	}
}

int swap_seats(int a, int b)
{
	pair<int, int> aPos = pos[a], bPos = pos[b];
	swap(grid[aPos.first][aPos.second], grid[bPos.first][bPos.second]);
	swap(pos[a], pos[b]);
	calcPrefix();
	return checkBeauty();
}

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