oj.uz

답안 #654325

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
654325 2022-10-31T02:18:51 Z buidangnguyen05 자리 배치 (IOI18_seats) C++14
17 / 100
 4000 ms 77648 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 s, int l, int r, int pos, int val) {
		if (l == r) {
			mx[s] = mi[s] = val;
			return;
		}
		int mid = (l + r) >> 1;
		if (pos <= mid) up(s << 1, l, mid, pos, val);
		else up(s << 1 | 1, mid + 1, r, pos, val);
		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(1, 1, m * n, x, row[y]);
		R.up(1, 1, m * n, y, row[x]);

		C.up(1, 1, m * n, x, col[y]);
		C.up(1, 1, m * n, 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(1, 1, m * n, x, row[y]);
		R.up(1, 1, m * n, y, row[x]);

		C.up(1, 1, m * n, x, col[y]);
		C.up(1, 1, m * n, 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(1, 1, m * n, i, row[i]);
		C.up(1, 1, m * n, i, col[i]);
	}

	for (int i = 1; i <= m * n; ++i) {
		R.up(1, 1, m * n, i, row[i]);
		C.up(1, 1, m * n, 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 3 ms 456 KB Output is correct
3 Correct 4 ms 452 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 4 ms 456 KB Output is correct
6 Correct 5 ms 452 KB Output is correct
7 Correct 4 ms 456 KB Output is correct
8 Correct 5 ms 536 KB Output is correct
9 Correct 4 ms 540 KB Output is correct
10 Correct 5 ms 460 KB Output is correct
11 Correct 4 ms 452 KB Output is correct
12 Correct 4 ms 452 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 3 ms 456 KB Output is correct
3 Correct 4 ms 452 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 4 ms 456 KB Output is correct
6 Correct 5 ms 452 KB Output is correct
7 Correct 4 ms 456 KB Output is correct
8 Correct 5 ms 536 KB Output is correct
9 Correct 4 ms 540 KB Output is correct
10 Correct 5 ms 460 KB Output is correct
11 Correct 4 ms 452 KB Output is correct
12 Correct 4 ms 452 KB Output is correct
13 Correct 60 ms 1336 KB Output is correct
14 Correct 66 ms 1348 KB Output is correct
15 Correct 60 ms 1340 KB Output is correct
16 Correct 58 ms 1332 KB Output is correct
17 Correct 60 ms 1348 KB Output is correct
18 Correct 60 ms 1348 KB Output is correct
19 Correct 60 ms 1360 KB Output is correct
20 Correct 60 ms 1332 KB Output is correct
21 Correct 58 ms 1344 KB Output is correct
22 Correct 58 ms 1344 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 589 ms 72684 KB Output is correct
2 Correct 622 ms 72772 KB Output is correct
3 Correct 3875 ms 75212 KB Output is correct
4 Correct 776 ms 74604 KB Output is correct
5 Correct 743 ms 72780 KB Output is correct
6 Execution timed out 4065 ms 76548 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 1344 KB Output is correct
2 Correct 130 ms 7916 KB Output is correct
3 Correct 649 ms 74104 KB Output is correct
4 Correct 672 ms 72788 KB Output is correct
5 Correct 670 ms 76616 KB Output is correct
6 Correct 665 ms 72780 KB Output is correct
7 Correct 668 ms 76572 KB Output is correct
8 Correct 661 ms 72636 KB Output is correct
9 Correct 662 ms 73060 KB Output is correct
10 Correct 681 ms 72672 KB Output is correct
11 Correct 679 ms 76584 KB Output is correct

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 2000 KB Output is correct
2 Correct 20 ms 2000 KB Output is correct
3 Correct 35 ms 1996 KB Output is correct
4 Correct 85 ms 2092 KB Output is correct
5 Correct 530 ms 2908 KB Output is correct
6 Correct 2925 ms 77588 KB Output is correct
7 Correct 2658 ms 73568 KB Output is correct
8 Correct 2624 ms 77648 KB Output is correct
9 Correct 759 ms 73520 KB Output is correct
10 Execution timed out 4083 ms 77472 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 3 ms 456 KB Output is correct
3 Correct 4 ms 452 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 4 ms 456 KB Output is correct
6 Correct 5 ms 452 KB Output is correct
7 Correct 4 ms 456 KB Output is correct
8 Correct 5 ms 536 KB Output is correct
9 Correct 4 ms 540 KB Output is correct
10 Correct 5 ms 460 KB Output is correct
11 Correct 4 ms 452 KB Output is correct
12 Correct 4 ms 452 KB Output is correct
13 Correct 60 ms 1336 KB Output is correct
14 Correct 66 ms 1348 KB Output is correct
15 Correct 60 ms 1340 KB Output is correct
16 Correct 58 ms 1332 KB Output is correct
17 Correct 60 ms 1348 KB Output is correct
18 Correct 60 ms 1348 KB Output is correct
19 Correct 60 ms 1360 KB Output is correct
20 Correct 60 ms 1332 KB Output is correct
21 Correct 58 ms 1344 KB Output is correct
22 Correct 58 ms 1344 KB Output is correct
23 Correct 589 ms 72684 KB Output is correct
24 Correct 622 ms 72772 KB Output is correct
25 Correct 3875 ms 75212 KB Output is correct
26 Correct 776 ms 74604 KB Output is correct
27 Correct 743 ms 72780 KB Output is correct
28 Execution timed out 4065 ms 76548 KB Time limit exceeded
29 Halted 0 ms 0 KB -