Submission #598319

#	Time	Username	Problem	Language	Result	Execution time	Memory
598319		jairRS	Seats (IOI18_seats)	C++17	0 / 100	4070 ms	39500 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 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;

	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			for (int k = i; k < h; k++)
				for (int l = j; l < w; l++)
				{
					ll area = (k - i + 1) * (l - j + 1);
					res += (getRectangleSum({i, j}, {k, l}) == area * (area - 1) / 2);
				}

	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]};
	}
	calcPrefix();
}

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]);
	return checkBeauty();
}

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