oj.uz

Submission #75747

# Submission time Handle Problem Language Result Execution time Memory
75747 2018-09-11T02:09:06 Z arock Seats (IOI18_seats) C++14
37 / 100
 4000 ms 57148 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

int H, W;
vector<int> R, C;

int ans = 1;
vector<int> lor, hir, loc, hic;

struct seg {
	int lr, hr, lc, hc;
} tree[4000000];

seg merge(seg a, seg b) {
	return {min(a.lr, b.lr), max(a.hr, b.hr), min(a.lc, b.lc), max(a.hc, b.hc)};
}

seg query(int l, int r, int cur, int lo, int hi) {

	if (l == lo && r == hi) {
		return tree[cur];
	}

	int lmid = (lo + hi) / 2, rmid = lmid + 1;
	if (r <= lmid) {
		return query(l, r, cur << 1 | 0, lo, lmid);
	} else if(l >= rmid) {
		return query(l, r, cur << 1 | 1, rmid, hi);
	} else {
		return merge(query(l, lmid, cur << 1 | 0, lo, lmid),
			         query(rmid, r, cur << 1 | 1, rmid, hi));
	}
}

void update(int pos, pair<int, int> val, int cur, int lo, int hi) {

	if (lo == hi) {
		tree[cur] = {val.first, val.first, val.second, val.second};
	} else {
		int lmid = (lo + hi) / 2, rmid = lmid + 1;
		if (pos <= lmid) {
			update(pos, val, cur << 1 | 0, lo, lmid);
		} else {
			update(pos, val, cur << 1 | 1, rmid, hi);
		}

		tree[cur] = merge(tree[cur << 1 | 0],
			              tree[cur << 1 | 1]);
	}
}


void give_initial_chart(int HH, int WW, vector<int> RR, vector<int> CC) {

	H = HH, W = WW, R = RR, C = CC;

	if (H <= 1000 && W <= 1000) {
		for (int i = 0; i < H * W; i++) {
			update(i + 1, {R[i], C[i]}, 1, 1, H * W);
		}
	} else {
		lor.resize(H * W), hir.resize(H * W);
		loc.resize(H * W), hic.resize(H * W);

		lor[0] = hir[0] = R[0];
		loc[0] = hic[0] = C[0];
		for (int i = 1; i < H * W; i++) {
			lor[i] = min(lor[i - 1], R[i]);
			hir[i] = max(hir[i - 1], R[i]);
			loc[i] = min(loc[i - 1], C[i]);
			hic[i] = max(hic[i - 1], C[i]);

			if ((hir[i] - lor[i] + 1) * (hic[i] - loc[i] + 1) == i + 1) {
				ans++;
			}
		}
	}
}


int swap_seats(int a, int b) {

	if (b < a) {
		swap(a, b);
	}

	swap(R[a], R[b]);
	swap(C[a], C[b]);

	if (H <= 1000 && W <= 1000) {
		update(a + 1, {R[a], C[a]}, 1, 1, H * W);
		update(b + 1, {R[b], C[b]}, 1, 1, H * W);

		int ans = 0, sz = 1;
		while (sz <= H * W) {
			seg s = query(1, sz, 1, 1, H * W);
			int box = (s.hr - s.lr + 1) * (s.hc - s.lc + 1);
			if (box == sz) {
				ans++, sz++;
			} else {
				sz = box;
			}
		}

		return ans;
	} else {
		for (int i = a; i <= min(H * W - 1, b + 1); i++) {
			if ((hir[i] - lor[i] + 1) * (hic[i] - loc[i] + 1) == i + 1) {
				ans--;
			}

			if (i == 0) {
				lor[i] = hir[i] = R[i];
				loc[i] = hic[i] = C[i];
			} else {
				lor[i] = min(lor[i - 1], R[i]);
				hir[i] = max(hir[i - 1], R[i]);
				loc[i] = min(loc[i - 1], C[i]);
				hic[i] = max(hic[i - 1], C[i]);			
			}

			if ((hir[i] - lor[i] + 1) * (hic[i] - loc[i] + 1) == i + 1) {
				ans++;
			}
		}

		return ans;
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 628 KB Output is correct
3 Correct 8 ms 628 KB Output is correct
4 Correct 6 ms 676 KB Output is correct
5 Correct 21 ms 772 KB Output is correct
6 Correct 5 ms 772 KB Output is correct
7 Correct 6 ms 796 KB Output is correct
8 Correct 7 ms 796 KB Output is correct
9 Correct 7 ms 796 KB Output is correct
10 Correct 6 ms 796 KB Output is correct
11 Correct 5 ms 796 KB Output is correct
12 Correct 21 ms 892 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 628 KB Output is correct
3 Correct 8 ms 628 KB Output is correct
4 Correct 6 ms 676 KB Output is correct
5 Correct 21 ms 772 KB Output is correct
6 Correct 5 ms 772 KB Output is correct
7 Correct 6 ms 796 KB Output is correct
8 Correct 7 ms 796 KB Output is correct
9 Correct 7 ms 796 KB Output is correct
10 Correct 6 ms 796 KB Output is correct
11 Correct 5 ms 796 KB Output is correct
12 Correct 21 ms 892 KB Output is correct
13 Correct 13 ms 1468 KB Output is correct
14 Correct 12 ms 1472 KB Output is correct
15 Correct 126 ms 1472 KB Output is correct
16 Correct 151 ms 1472 KB Output is correct
17 Correct 185 ms 1472 KB Output is correct
18 Correct 463 ms 1480 KB Output is correct
19 Correct 1117 ms 1596 KB Output is correct
20 Correct 128 ms 1596 KB Output is correct
21 Correct 129 ms 1596 KB Output is correct
22 Correct 127 ms 1596 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 57148 KB Output is correct
2 Correct 541 ms 57148 KB Output is correct
3 Correct 2856 ms 57148 KB Output is correct
4 Correct 632 ms 57148 KB Output is correct
5 Correct 610 ms 57148 KB Output is correct
6 Correct 3224 ms 57148 KB Output is correct
7 Correct 1115 ms 57148 KB Output is correct
8 Correct 707 ms 57148 KB Output is correct
9 Correct 2787 ms 57148 KB Output is correct
10 Correct 1743 ms 57148 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 57148 KB Output is correct
2 Correct 89 ms 57148 KB Output is correct
3 Correct 2559 ms 57148 KB Output is correct
4 Correct 605 ms 57148 KB Output is correct
5 Correct 656 ms 57148 KB Output is correct
6 Correct 654 ms 57148 KB Output is correct
7 Correct 649 ms 57148 KB Output is correct
8 Correct 639 ms 57148 KB Output is correct
9 Correct 628 ms 57148 KB Output is correct
10 Correct 641 ms 57148 KB Output is correct
11 Correct 650 ms 57148 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 57148 KB Output is correct
2 Correct 33 ms 57148 KB Output is correct
3 Correct 251 ms 57148 KB Output is correct
4 Correct 2774 ms 57148 KB Output is correct
5 Correct 1205 ms 57148 KB Output is correct
6 Execution timed out 4014 ms 57148 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 628 KB Output is correct
3 Correct 8 ms 628 KB Output is correct
4 Correct 6 ms 676 KB Output is correct
5 Correct 21 ms 772 KB Output is correct
6 Correct 5 ms 772 KB Output is correct
7 Correct 6 ms 796 KB Output is correct
8 Correct 7 ms 796 KB Output is correct
9 Correct 7 ms 796 KB Output is correct
10 Correct 6 ms 796 KB Output is correct
11 Correct 5 ms 796 KB Output is correct
12 Correct 21 ms 892 KB Output is correct
13 Correct 13 ms 1468 KB Output is correct
14 Correct 12 ms 1472 KB Output is correct
15 Correct 126 ms 1472 KB Output is correct
16 Correct 151 ms 1472 KB Output is correct
17 Correct 185 ms 1472 KB Output is correct
18 Correct 463 ms 1480 KB Output is correct
19 Correct 1117 ms 1596 KB Output is correct
20 Correct 128 ms 1596 KB Output is correct
21 Correct 129 ms 1596 KB Output is correct
22 Correct 127 ms 1596 KB Output is correct
23 Correct 540 ms 57148 KB Output is correct
24 Correct 541 ms 57148 KB Output is correct
25 Correct 2856 ms 57148 KB Output is correct
26 Correct 632 ms 57148 KB Output is correct
27 Correct 610 ms 57148 KB Output is correct
28 Correct 3224 ms 57148 KB Output is correct
29 Correct 1115 ms 57148 KB Output is correct
30 Correct 707 ms 57148 KB Output is correct
31 Correct 2787 ms 57148 KB Output is correct
32 Correct 1743 ms 57148 KB Output is correct
33 Correct 11 ms 57148 KB Output is correct
34 Correct 89 ms 57148 KB Output is correct
35 Correct 2559 ms 57148 KB Output is correct
36 Correct 605 ms 57148 KB Output is correct
37 Correct 656 ms 57148 KB Output is correct
38 Correct 654 ms 57148 KB Output is correct
39 Correct 649 ms 57148 KB Output is correct
40 Correct 639 ms 57148 KB Output is correct
41 Correct 628 ms 57148 KB Output is correct
42 Correct 641 ms 57148 KB Output is correct
43 Correct 650 ms 57148 KB Output is correct
44 Correct 25 ms 57148 KB Output is correct
45 Correct 33 ms 57148 KB Output is correct
46 Correct 251 ms 57148 KB Output is correct
47 Correct 2774 ms 57148 KB Output is correct
48 Correct 1205 ms 57148 KB Output is correct
49 Execution timed out 4014 ms 57148 KB Time limit exceeded
50 Halted 0 ms 0 KB -