oj.uz

Submission #654331

# Submission time Handle Problem Language Result Execution time Memory
654331 2022-10-31T02:54:51 Z buidangnguyen05 Seats (IOI18_seats) C++17
17 / 100
 4000 ms 61972 KB 
//source:

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e6 + 10;
int row[N], col[N], ans[N];

int res;
bool sub4 = 1;

int n, m, q;
vector<pair<int, int>> query;

struct SegmentTree {
	int mx[4 * N], mi[4 * N];

	void up(int pos, int val) {
		int s = 1, l = 1, r = m * n;
		while (l != r) {
			int mid = (l + r) >> 1;
			if (pos <= mid) s = s << 1, r = mid;
			else s = s << 1 | 1, l = mid + 1;
		}

		mx[s] = mi[s] = val;
		while (s != 1) {
			s >>= 1;
			mx[s] = max(mx[s << 1], mx[s << 1 | 1]);
			mi[s] = min(mi[s << 1], mi[s << 1 | 1]);
		}
	}

	pair<int, int> get(int s, int l, int r, int u, int v) {
		if (l > v || r < u || u > v) return make_pair(1e9, 0);
		if (l >= u && r <= v) return make_pair(mi[s], mx[s]);
		int mid = (l + r) >> 1;
		pair<int, int> L = get(s << 1, l, mid, u, v), R = get(s << 1 | 1, mid + 1, r, u, v);
		return make_pair(min(L.first, R.first), max(L.second, R.second));
	}
} R, C;

int swap_seats(int x, int y) {
	if (x > y) swap(x, y);
	++x; ++y;

	if (sub4 && y - x <= 1e4) {
		R.up(x, row[y]);
		R.up(y, row[x]);

		C.up(x, col[y]);
		C.up(y, col[x]);

		swap(row[x], row[y]); swap(col[x], col[y]);

		int miR, mxR, miC, mxC;
		tie(miR, mxR) = R.get(1, 1, m * n, 1, x - 1); tie(miC, mxC) = C.get(1, 1, m * n, 1, x - 1);

		for (int i = x; i <= y; ++i) {
			mxR = max(mxR, row[i]);
			miR = min(miR, row[i]);
			mxC = max(mxC, col[i]);
			miC = min(miC, col[i]);

			int nans = (mxR - miR + 1) * (mxC - miC + 1) == i;

			res += nans - ans[i];
			ans[i] = nans;
		}
		return res;
	}
	else {
		sub4 = 0;

		R.up(x, row[y]);
		R.up(y, row[x]);

		C.up(x, col[y]);
		C.up(y, col[x]);

		swap(row[x], row[y]); swap(col[x], col[y]);

		int mxR = 0, miR = 1e9, mxC = 0, miC = 1e9; res = 0;
		for (int i = 1; i <= m * n; ++i) {
			tie(miR, mxR) = R.get(1, 1, m * n, 1, i); tie(miC, mxC) = C.get(1, 1, m * n, 1, i);

			if ((mxR - miR + 1) * (mxC - miC + 1) == i) ++res;
			else i = (mxR - miR + 1) * (mxC - miC + 1) - 1;
		}
		return res;
	}
}

void give_initial_chart(int H, int W, vector<int> _R, vector<int> _C) {
	m = H, n = W;
	for (int i = 1; i <= m * n; ++i) {
		row[i] = _R[i - 1]; col[i] = _C[i - 1];
		++row[i]; ++col[i];
	}

	for (int i = 1; i <= m * n; ++i) {
		R.up(i, row[i]);
		C.up(i, col[i]);
	}

	int mxR = 0, miR = 1e9, mxC = 0, miC = 1e9;
	for (int i = 1; i <= m * n; ++i) {
		mxR = max(mxR, row[i]);
		miR = min(miR, row[i]);
		mxC = max(mxC, col[i]);
		miC = min(miC, col[i]);

		if ((mxR - miR + 1) * (mxC - miC + 1) == i) ans[i] = 1, ++res;
	}
}

// ඞඞඞඞඞ you sus

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 4 ms 536 KB Output is correct
3 Correct 5 ms 456 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 5 ms 452 KB Output is correct
10 Correct 5 ms 460 KB Output is correct
11 Correct 5 ms 468 KB Output is correct
12 Correct 5 ms 452 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 4 ms 536 KB Output is correct
3 Correct 5 ms 456 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 5 ms 452 KB Output is correct
10 Correct 5 ms 460 KB Output is correct
11 Correct 5 ms 468 KB Output is correct
12 Correct 5 ms 452 KB Output is correct
13 Correct 73 ms 1356 KB Output is correct
14 Correct 66 ms 1344 KB Output is correct
15 Correct 64 ms 1340 KB Output is correct
16 Correct 76 ms 1340 KB Output is correct
17 Correct 78 ms 1328 KB Output is correct
18 Correct 60 ms 1356 KB Output is correct
19 Correct 61 ms 1344 KB Output is correct
20 Correct 59 ms 1336 KB Output is correct
21 Correct 61 ms 1344 KB Output is correct
22 Correct 66 ms 1344 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 57700 KB Output is correct
2 Correct 541 ms 57724 KB Output is correct
3 Execution timed out 4061 ms 60548 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 1364 KB Output is correct
2 Correct 125 ms 7048 KB Output is correct
3 Correct 557 ms 59188 KB Output is correct
4 Correct 555 ms 57852 KB Output is correct
5 Correct 539 ms 61736 KB Output is correct
6 Correct 556 ms 57804 KB Output is correct
7 Correct 533 ms 61576 KB Output is correct
8 Correct 552 ms 57908 KB Output is correct
9 Correct 592 ms 58256 KB Output is correct
10 Correct 569 ms 57748 KB Output is correct
11 Correct 546 ms 61656 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1704 KB Output is correct
2 Correct 23 ms 1736 KB Output is correct
3 Correct 33 ms 1736 KB Output is correct
4 Correct 100 ms 1764 KB Output is correct
5 Correct 656 ms 2440 KB Output is correct
6 Correct 3359 ms 61880 KB Output is correct
7 Correct 3015 ms 58184 KB Output is correct
8 Correct 2856 ms 61948 KB Output is correct
9 Correct 680 ms 58008 KB Output is correct
10 Execution timed out 4030 ms 61972 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 4 ms 536 KB Output is correct
3 Correct 5 ms 456 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 5 ms 452 KB Output is correct
10 Correct 5 ms 460 KB Output is correct
11 Correct 5 ms 468 KB Output is correct
12 Correct 5 ms 452 KB Output is correct
13 Correct 73 ms 1356 KB Output is correct
14 Correct 66 ms 1344 KB Output is correct
15 Correct 64 ms 1340 KB Output is correct
16 Correct 76 ms 1340 KB Output is correct
17 Correct 78 ms 1328 KB Output is correct
18 Correct 60 ms 1356 KB Output is correct
19 Correct 61 ms 1344 KB Output is correct
20 Correct 59 ms 1336 KB Output is correct
21 Correct 61 ms 1344 KB Output is correct
22 Correct 66 ms 1344 KB Output is correct
23 Correct 451 ms 57700 KB Output is correct
24 Correct 541 ms 57724 KB Output is correct
25 Execution timed out 4061 ms 60548 KB Time limit exceeded
26 Halted 0 ms 0 KB -