oj.uz

Submission #535853

# Submission time Handle Problem Language Result Execution time Memory
535853 2022-03-11T14:38:10 Z LucaDantas Seats (IOI18_seats) C++17
5 / 100
 4000 ms 88300 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 1<<20;

struct SegmentTree {
	int tree[maxn<<1], a[maxn], trash;
	bool op; // op = 0 -> min, op = 1 -> max
	SegmentTree(bool _op) : op(_op) { trash = _op == 0 ? maxn : -maxn; }
	int comb(int a, int b) { return ((a < b) ^ op) ? a : b; }

	void build(int node, int i, int j) {
		if(i == j) return (void)(tree[node] = a[i]);
		int m = (i+j) >> 1;
		build(node<<1, i, m); build(node<<1|1, m+1, j);
		tree[node] = comb(tree[node<<1], tree[node<<1|1]);
	}

	void upd(int node, int i, int j, int pos, int v) {
		if(i == j) return (void)(tree[node] = v);
		int m = (i+j) >> 1;
		if(pos <= m) upd(node<<1, i, m, pos, v);
		else upd(node<<1|1, m+1, j, pos, v);
		tree[node] = comb(tree[node<<1], tree[node<<1|1]);
	}

	int query(int node, int i, int j, int r) {
		if(i > r) return trash;
		if(j <= r) return tree[node];
		int m = (i+j) >> 1;
		return comb(query(node<<1, i, m, r), query(node<<1|1, m+1, j, r));
	}
} R1(0), C1(0), R2(1), C2(1);

int n, h, w;
vector<int> r, c;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	n = H*W; h = W, w = W;
	r = R, c = C;

	for(int i = 0; i < n; i++)
		R1.a[i] = R[i], R2.a[i] = R[i], C1.a[i] = C[i], C2.a[i] = C[i];

	R1.build(1, 0, n-1);
	R2.build(1, 0, n-1);
	C1.build(1, 0, n-1);
	C2.build(1, 0, n-1);
}

int swap_seats(int a, int b) {
	swap(r[a], r[b]), swap(c[a], c[b]);

	for(int i = 0; i < 2; i++, swap(a, b)) {
		R1.upd(1, 0, n-1, a, r[a]);
		R2.upd(1, 0, n-1, a, r[a]);
		C1.upd(1, 0, n-1, a, c[a]);
		C2.upd(1, 0, n-1, a, c[a]);
	}

	int ans = 0, pos = 0;
	while(pos < n) {
		int sz = (R2.query(1, 0, n-1, pos) - R1.query(1, 0, n-1, pos) + 1) *
			(C2.query(1, 0, n-1, pos) - C1.query(1, 0, n-1, pos) + 1);

		if(pos == sz-1) ++ans, ++pos;
		else pos = sz-1;
	}

	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 6 ms 456 KB Output is correct
3 Correct 7 ms 472 KB Output is correct
4 Correct 5 ms 472 KB Output is correct
5 Correct 34 ms 484 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 5 ms 544 KB Output is correct
8 Correct 8 ms 464 KB Output is correct
9 Correct 7 ms 468 KB Output is correct
10 Correct 5 ms 468 KB Output is correct
11 Correct 4 ms 472 KB Output is correct
12 Correct 32 ms 484 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 6 ms 456 KB Output is correct
3 Correct 7 ms 472 KB Output is correct
4 Correct 5 ms 472 KB Output is correct
5 Correct 34 ms 484 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 5 ms 544 KB Output is correct
8 Correct 8 ms 464 KB Output is correct
9 Correct 7 ms 468 KB Output is correct
10 Correct 5 ms 468 KB Output is correct
11 Correct 4 ms 472 KB Output is correct
12 Correct 32 ms 484 KB Output is correct
13 Correct 20 ms 1476 KB Output is correct
14 Correct 11 ms 1488 KB Output is correct
15 Correct 11 ms 1488 KB Output is correct
16 Execution timed out 4054 ms 1364 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 72280 KB Output is correct
2 Correct 325 ms 72284 KB Output is correct
3 Execution timed out 4041 ms 88268 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1236 KB Output is correct
2 Correct 111 ms 9328 KB Output is correct
3 Execution timed out 4067 ms 88300 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1348 KB Output is correct
2 Correct 28 ms 1328 KB Output is correct
3 Correct 371 ms 2024 KB Output is correct
4 Execution timed out 4050 ms 2036 KB Time limit exceeded
5 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 6 ms 456 KB Output is correct
3 Correct 7 ms 472 KB Output is correct
4 Correct 5 ms 472 KB Output is correct
5 Correct 34 ms 484 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 5 ms 544 KB Output is correct
8 Correct 8 ms 464 KB Output is correct
9 Correct 7 ms 468 KB Output is correct
10 Correct 5 ms 468 KB Output is correct
11 Correct 4 ms 472 KB Output is correct
12 Correct 32 ms 484 KB Output is correct
13 Correct 20 ms 1476 KB Output is correct
14 Correct 11 ms 1488 KB Output is correct
15 Correct 11 ms 1488 KB Output is correct
16 Execution timed out 4054 ms 1364 KB Time limit exceeded
17 Halted 0 ms 0 KB -