oj.uz

Submission #75744

# Submission time Handle Problem Language Result Execution time Memory
75744 2018-09-11T01:55:07 Z arock Seats (IOI18_seats) C++14
25 / 100
 4000 ms 57712 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

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

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;

	for (int i = 0; i < H * W; i++) {
		update(i + 1, {R[i], C[i]}, 1, 1, H * W);
	}
}


int swap_seats(int a, int b) {

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

	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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 6 ms 508 KB Output is correct
3 Correct 5 ms 584 KB Output is correct
4 Correct 6 ms 616 KB Output is correct
5 Correct 22 ms 680 KB Output is correct
6 Correct 6 ms 680 KB Output is correct
7 Correct 6 ms 680 KB Output is correct
8 Correct 7 ms 680 KB Output is correct
9 Correct 8 ms 756 KB Output is correct
10 Correct 6 ms 756 KB Output is correct
11 Correct 5 ms 756 KB Output is correct
12 Correct 21 ms 756 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 6 ms 508 KB Output is correct
3 Correct 5 ms 584 KB Output is correct
4 Correct 6 ms 616 KB Output is correct
5 Correct 22 ms 680 KB Output is correct
6 Correct 6 ms 680 KB Output is correct
7 Correct 6 ms 680 KB Output is correct
8 Correct 7 ms 680 KB Output is correct
9 Correct 8 ms 756 KB Output is correct
10 Correct 6 ms 756 KB Output is correct
11 Correct 5 ms 756 KB Output is correct
12 Correct 21 ms 756 KB Output is correct
13 Correct 13 ms 1412 KB Output is correct
14 Correct 11 ms 1412 KB Output is correct
15 Correct 13 ms 1412 KB Output is correct
16 Execution timed out 4011 ms 1540 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 824 ms 57132 KB Output is correct
2 Correct 546 ms 57132 KB Output is correct
3 Correct 2779 ms 57132 KB Output is correct
4 Correct 624 ms 57132 KB Output is correct
5 Correct 608 ms 57132 KB Output is correct
6 Correct 3076 ms 57132 KB Output is correct
7 Correct 1096 ms 57132 KB Output is correct
8 Correct 671 ms 57260 KB Output is correct
9 Correct 2813 ms 57260 KB Output is correct
10 Correct 1808 ms 57260 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 57260 KB Output is correct
2 Correct 85 ms 57260 KB Output is correct
3 Correct 2525 ms 57260 KB Output is correct
4 Correct 535 ms 57260 KB Output is correct
5 Execution timed out 4027 ms 57260 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 57260 KB Output is correct
2 Correct 31 ms 57260 KB Output is correct
3 Correct 200 ms 57260 KB Output is correct
4 Correct 2565 ms 57260 KB Output is correct
5 Correct 65 ms 57260 KB Output is correct
6 Correct 2043 ms 57404 KB Output is correct
7 Correct 1806 ms 57404 KB Output is correct
8 Correct 1790 ms 57460 KB Output is correct
9 Correct 646 ms 57460 KB Output is correct
10 Execution timed out 4011 ms 57712 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 6 ms 508 KB Output is correct
3 Correct 5 ms 584 KB Output is correct
4 Correct 6 ms 616 KB Output is correct
5 Correct 22 ms 680 KB Output is correct
6 Correct 6 ms 680 KB Output is correct
7 Correct 6 ms 680 KB Output is correct
8 Correct 7 ms 680 KB Output is correct
9 Correct 8 ms 756 KB Output is correct
10 Correct 6 ms 756 KB Output is correct
11 Correct 5 ms 756 KB Output is correct
12 Correct 21 ms 756 KB Output is correct
13 Correct 13 ms 1412 KB Output is correct
14 Correct 11 ms 1412 KB Output is correct
15 Correct 13 ms 1412 KB Output is correct
16 Execution timed out 4011 ms 1540 KB Time limit exceeded
17 Halted 0 ms 0 KB -