oj.uz

Submission #598322

# Submission time Handle Problem Language Result Execution time Memory
598322 2022-07-18T04:20:21 Z jairRS Seats (IOI18_seats) C++17
11 / 100
 4000 ms 39480 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 7 ms 380 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 6 ms 372 KB Output is correct
8 Correct 7 ms 340 KB Output is correct
9 Correct 7 ms 416 KB Output is correct
10 Correct 6 ms 340 KB Output is correct
11 Correct 7 ms 340 KB Output is correct
12 Correct 7 ms 340 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 7 ms 380 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 6 ms 372 KB Output is correct
8 Correct 7 ms 340 KB Output is correct
9 Correct 7 ms 416 KB Output is correct
10 Correct 6 ms 340 KB Output is correct
11 Correct 7 ms 340 KB Output is correct
12 Correct 7 ms 340 KB Output is correct
13 Correct 498 ms 724 KB Output is correct
14 Correct 516 ms 900 KB Output is correct
15 Correct 470 ms 880 KB Output is correct
16 Correct 610 ms 1852 KB Output is correct
17 Correct 472 ms 936 KB Output is correct
18 Correct 505 ms 904 KB Output is correct
19 Correct 484 ms 980 KB Output is correct
20 Correct 584 ms 1288 KB Output is correct
21 Correct 500 ms 900 KB Output is correct
22 Correct 672 ms 1844 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4077 ms 39480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 724 KB Output is correct
2 Execution timed out 4034 ms 5084 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1328 KB Output is correct
2 Correct 19 ms 1336 KB Output is correct
3 Correct 66 ms 1312 KB Output is correct
4 Correct 488 ms 1260 KB Output is correct
5 Execution timed out 4043 ms 2336 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 7 ms 380 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 6 ms 372 KB Output is correct
8 Correct 7 ms 340 KB Output is correct
9 Correct 7 ms 416 KB Output is correct
10 Correct 6 ms 340 KB Output is correct
11 Correct 7 ms 340 KB Output is correct
12 Correct 7 ms 340 KB Output is correct
13 Correct 498 ms 724 KB Output is correct
14 Correct 516 ms 900 KB Output is correct
15 Correct 470 ms 880 KB Output is correct
16 Correct 610 ms 1852 KB Output is correct
17 Correct 472 ms 936 KB Output is correct
18 Correct 505 ms 904 KB Output is correct
19 Correct 484 ms 980 KB Output is correct
20 Correct 584 ms 1288 KB Output is correct
21 Correct 500 ms 900 KB Output is correct
22 Correct 672 ms 1844 KB Output is correct
23 Execution timed out 4077 ms 39480 KB Time limit exceeded
24 Halted 0 ms 0 KB -