oj.uz

Submission #630379

# Submission time Handle Problem Language Result Execution time Memory
630379 2022-08-16T09:46:02 Z abeker Seats (IOI18_seats) C++17
100 / 100
 2844 ms 228784 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair <int, int> pii;

const int MAXN = 1e6 + 5;
const int offset = 1 << 20;
const int INF = 1e9;

const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};

struct node {
	int mini, occ, lazy;
};
	
struct tournament {
	node t[2 * offset];
	
	node merge(node l, node r) {
		node res;
		res.mini = min(l.mini, r.mini);
		res.occ = 0;
		if (l.mini == res.mini)
			res.occ += l.occ;
		if (r.mini == res.mini)
			res.occ += r.occ;
		res.lazy = l.lazy + r.lazy;
		return res;
	}
	
	void init(int n) {
		for (int i = 0; i < offset; i++)	
			t[i + offset] = {i < n ? -1 : INF, 1, 0};
		for (int i = offset - 1; i >= 0; i--)
			t[i] = merge(t[2 * i], t[2 * i + 1]);
	}
	
	void prop(int x) {
		t[x].mini += t[x].lazy;
		if (x < offset) {
			t[2 * x].lazy += t[x].lazy;
			t[2 * x + 1].lazy += t[x].lazy;
		}
		t[x].lazy = 0;
	}
	
	void update(int x, int lo, int hi, int from, int to, int val) {
		prop(x);
		if (lo >= to || hi <= from)
			return;
		if (lo >= from && hi <= to) {
			t[x].mini += val;
			if (x < offset) {
				t[2 * x].lazy += val;
				t[2 * x + 1].lazy += val;
			}
			return;
		}
		int mid = (lo + hi) / 2;
		update(2 * x, lo, mid, from, to, val);
		update(2 * x + 1, mid, hi, from, to, val);
		t[x] = merge(t[2 * x], t[2 * x + 1]);
	}
	
	node query(int x, int lo, int hi, int from, int to) {
		prop(x);
		if (lo >= to || hi <= from)
			return {INF, 1, 0};
		if (lo >= from && hi <= to)
			return t[x];
		int mid = (lo + hi) / 2;
		return merge(query(2 * x, lo, mid, from, to), query(2 * x + 1, mid, hi, from, to));
	}
	
	void update(int from, int to) {
		if (from < to)
			update(1, 0, offset, from, to, 1);
		else
			update(1, 0, offset, to, from, -1);
	}
	
	int query(int from, int to) {
		node tmp = query(1, 0, offset, from, to);
		return tmp.mini ? 0 : tmp.occ;
	}
};

int N, H, W;
vector <int> r, c;
vector < vector <int> > mat, mn1, mn2;
tournament T;

bool ok(int x, int y) {
	return x > 0 && y > 0 && x <= H && y <= W;
}

void change(int x, int y) {
	int old = mn1[x][y];
	mn1[x][y] = max(min(mat[x - 1][y], mat[x][y - 1]), mat[x][y]);
	T.update(old, mn1[x][y]);
	
	vector <int> adj;
	for (int i = 0; i < 4; i++)
		adj.push_back(mat[x + dx[i]][y + dy[i]]);
	
	sort(adj.begin(), adj.end());
	
	old = mn2[x][y];
	mn2[x][y] = min(adj[1], mat[x][y]);
	T.update(mn2[x][y], old);
}

void update_all(int x, int y) {
	change(x, y);
	for (int i = 0; i < 4; i++)
		if (ok(x + dx[i], y + dy[i]))
			change(x + dx[i], y + dy[i]);
}

void give_initial_chart(int h, int w, vector <int> R, vector <int> C) {
	H = h;
	W = w;
	r = R;
	c = C;
	N = H * W;
	T.init(N);
	
	mat.resize(H + 2);
	mn1.resize(H + 2);
	mn2.resize(H + 2);
	for (int i = 0; i < H + 2; i++) 
		mat[i] = mn1[i] = mn2[i] = vector <int> (W + 2, N);
	
	for (int i = 0; i < N; i++) {
		r[i]++; c[i]++;
		mat[r[i]][c[i]] = mn1[r[i]][c[i]] = mn2[r[i]][c[i]] = i;
	}
	
	for (int i = 1; i <= H; i++)
		for (int j = 1; j <= W; j++)
			change(i, j);	
}

int swap_seats(int a, int b) {
	swap(mat[r[a]][c[a]], mat[r[b]][c[b]]);
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	
	update_all(r[a], c[a]);
	update_all(r[b], c[b]);
  
  return T.query(0, N);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 25036 KB Output is correct
2 Correct 49 ms 25068 KB Output is correct
3 Correct 58 ms 25024 KB Output is correct
4 Correct 43 ms 25064 KB Output is correct
5 Correct 40 ms 25184 KB Output is correct
6 Correct 48 ms 25056 KB Output is correct
7 Correct 49 ms 25036 KB Output is correct
8 Correct 64 ms 25036 KB Output is correct
9 Correct 49 ms 25020 KB Output is correct
10 Correct 48 ms 25048 KB Output is correct
11 Correct 55 ms 25032 KB Output is correct
12 Correct 38 ms 25028 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 25036 KB Output is correct
2 Correct 49 ms 25068 KB Output is correct
3 Correct 58 ms 25024 KB Output is correct
4 Correct 43 ms 25064 KB Output is correct
5 Correct 40 ms 25184 KB Output is correct
6 Correct 48 ms 25056 KB Output is correct
7 Correct 49 ms 25036 KB Output is correct
8 Correct 64 ms 25036 KB Output is correct
9 Correct 49 ms 25020 KB Output is correct
10 Correct 48 ms 25048 KB Output is correct
11 Correct 55 ms 25032 KB Output is correct
12 Correct 38 ms 25028 KB Output is correct
13 Correct 70 ms 25428 KB Output is correct
14 Correct 79 ms 25484 KB Output is correct
15 Correct 57 ms 25700 KB Output is correct
16 Correct 51 ms 27028 KB Output is correct
17 Correct 65 ms 25592 KB Output is correct
18 Correct 65 ms 25492 KB Output is correct
19 Correct 64 ms 25636 KB Output is correct
20 Correct 55 ms 26196 KB Output is correct
21 Correct 51 ms 25644 KB Output is correct
22 Correct 54 ms 26964 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1841 ms 76332 KB Output is correct
2 Correct 1177 ms 76332 KB Output is correct
3 Correct 1317 ms 76280 KB Output is correct
4 Correct 1016 ms 76284 KB Output is correct
5 Correct 1170 ms 76312 KB Output is correct
6 Correct 1077 ms 76280 KB Output is correct
7 Correct 1105 ms 76280 KB Output is correct
8 Correct 1149 ms 76336 KB Output is correct
9 Correct 1080 ms 76276 KB Output is correct
10 Correct 1096 ms 76276 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 25500 KB Output is correct
2 Correct 158 ms 29388 KB Output is correct
3 Correct 1046 ms 76288 KB Output is correct
4 Correct 1874 ms 76280 KB Output is correct
5 Correct 1008 ms 99696 KB Output is correct
6 Correct 2043 ms 228784 KB Output is correct
7 Correct 1078 ms 84000 KB Output is correct
8 Correct 1173 ms 76464 KB Output is correct
9 Correct 1068 ms 77316 KB Output is correct
10 Correct 1096 ms 90224 KB Output is correct
11 Correct 1083 ms 146500 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 26548 KB Output is correct
2 Correct 235 ms 26624 KB Output is correct
3 Correct 251 ms 26520 KB Output is correct
4 Correct 326 ms 26592 KB Output is correct
5 Correct 335 ms 27272 KB Output is correct
6 Correct 1356 ms 100656 KB Output is correct
7 Correct 1440 ms 100600 KB Output is correct
8 Correct 1368 ms 100652 KB Output is correct
9 Correct 2004 ms 100596 KB Output is correct
10 Correct 1327 ms 100604 KB Output is correct
11 Correct 1347 ms 100616 KB Output is correct
12 Correct 1239 ms 100600 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 25036 KB Output is correct
2 Correct 49 ms 25068 KB Output is correct
3 Correct 58 ms 25024 KB Output is correct
4 Correct 43 ms 25064 KB Output is correct
5 Correct 40 ms 25184 KB Output is correct
6 Correct 48 ms 25056 KB Output is correct
7 Correct 49 ms 25036 KB Output is correct
8 Correct 64 ms 25036 KB Output is correct
9 Correct 49 ms 25020 KB Output is correct
10 Correct 48 ms 25048 KB Output is correct
11 Correct 55 ms 25032 KB Output is correct
12 Correct 38 ms 25028 KB Output is correct
13 Correct 70 ms 25428 KB Output is correct
14 Correct 79 ms 25484 KB Output is correct
15 Correct 57 ms 25700 KB Output is correct
16 Correct 51 ms 27028 KB Output is correct
17 Correct 65 ms 25592 KB Output is correct
18 Correct 65 ms 25492 KB Output is correct
19 Correct 64 ms 25636 KB Output is correct
20 Correct 55 ms 26196 KB Output is correct
21 Correct 51 ms 25644 KB Output is correct
22 Correct 54 ms 26964 KB Output is correct
23 Correct 1841 ms 76332 KB Output is correct
24 Correct 1177 ms 76332 KB Output is correct
25 Correct 1317 ms 76280 KB Output is correct
26 Correct 1016 ms 76284 KB Output is correct
27 Correct 1170 ms 76312 KB Output is correct
28 Correct 1077 ms 76280 KB Output is correct
29 Correct 1105 ms 76280 KB Output is correct
30 Correct 1149 ms 76336 KB Output is correct
31 Correct 1080 ms 76276 KB Output is correct
32 Correct 1096 ms 76276 KB Output is correct
33 Correct 66 ms 25500 KB Output is correct
34 Correct 158 ms 29388 KB Output is correct
35 Correct 1046 ms 76288 KB Output is correct
36 Correct 1874 ms 76280 KB Output is correct
37 Correct 1008 ms 99696 KB Output is correct
38 Correct 2043 ms 228784 KB Output is correct
39 Correct 1078 ms 84000 KB Output is correct
40 Correct 1173 ms 76464 KB Output is correct
41 Correct 1068 ms 77316 KB Output is correct
42 Correct 1096 ms 90224 KB Output is correct
43 Correct 1083 ms 146500 KB Output is correct
44 Correct 209 ms 26548 KB Output is correct
45 Correct 235 ms 26624 KB Output is correct
46 Correct 251 ms 26520 KB Output is correct
47 Correct 326 ms 26592 KB Output is correct
48 Correct 335 ms 27272 KB Output is correct
49 Correct 1356 ms 100656 KB Output is correct
50 Correct 1440 ms 100600 KB Output is correct
51 Correct 1368 ms 100652 KB Output is correct
52 Correct 2004 ms 100596 KB Output is correct
53 Correct 1327 ms 100604 KB Output is correct
54 Correct 1347 ms 100616 KB Output is correct
55 Correct 1239 ms 100600 KB Output is correct
56 Correct 326 ms 26524 KB Output is correct
57 Correct 390 ms 26584 KB Output is correct
58 Correct 480 ms 26964 KB Output is correct
59 Correct 1798 ms 77240 KB Output is correct
60 Correct 2342 ms 77244 KB Output is correct
61 Correct 1629 ms 77248 KB Output is correct
62 Correct 1418 ms 88864 KB Output is correct
63 Correct 2255 ms 84908 KB Output is correct
64 Correct 1789 ms 79524 KB Output is correct
65 Correct 1865 ms 77328 KB Output is correct
66 Correct 2103 ms 78248 KB Output is correct
67 Correct 1927 ms 91192 KB Output is correct
68 Correct 1624 ms 120168 KB Output is correct
69 Correct 2844 ms 147552 KB Output is correct