oj.uz

Submission #423124

# Submission time Handle Problem Language Result Execution time Memory
423124 2021-06-10T18:15:38 Z jtnydv25 Seats (IOI18_seats) C++17
100 / 100
 2999 ms 149276 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())

#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl '\n'
#endif

// min, min_count segtree
struct Data{
	int mn, mncnt;
	Data() : mn(0), mncnt(1){}
	Data(int mn, int mncnt) : mn(mn), mncnt(mncnt){}
};
Data merge(const Data & A, const Data & B){
	Data ret;
	ret.mn = min(A.mn, B.mn);
	ret.mncnt = (A.mn == ret.mn ? A.mncnt : 0) + (B.mn == ret.mn ? B.mncnt : 0);
	return ret;
}

struct segtree{
	vector<Data> tree;
	vector<int> lazy;
	int n;
	segtree(){}
	segtree(vector<int> vals) : n(vals.size()){
		tree.resize(4 * n);
		lazy.resize(4 * n);
		function<void(int, int, int)> make = [&](int s, int e, int ind){
			if(s == e){
				tree[ind] = Data(vals[s], 1);
				return;
			}
			int mid = (s + e) >> 1;
			make(s, mid, 2 * ind);
			make(mid + 1, e, 2 * ind + 1);
			tree[ind] = merge(tree[2 * ind], tree[2 * ind + 1]);
		};
		make(0, n - 1, 1);
	}
	void push(int s, int e, int ind){
		int l = lazy[ind];
		if(l == 0) return;
		tree[ind].mn += l;
		if(s != e){
			lazy[2 * ind] += l;
			lazy[2 * ind + 1] += l;
		}
		lazy[ind] = 0;
	}
	void add(int L, int R, int v, int s, int e, int ind){
		push(s, e, ind);
		if(L > e || s > R) return;
		if(s >= L && e <= R){
			lazy[ind] += v;
			push(s, e, ind);
			return;
		}
		int mid = (s + e) >> 1;
		add(L, R, v, s, mid, 2 * ind);
		add(L, R, v, mid + 1, e, 2 * ind + 1);
		tree[ind] = merge(tree[2 * ind], tree[2 * ind + 1]);
	}
	void add(int L, int R, int v){
		R = min(R, n - 1);
		if(L > R) return;
		add(L, R, v, 0, n - 1, 1);
	}
};

int H, W;
vector<int> R, C;
vector<vector<int>> when;
segtree st;
vector<int> init;
void add_contribution(int i, int j, int k, bool flag = 0){
	vector<int> times;
	for(int _i : {i, i + 1}) for(int _j : {j, j + 1}){
		times.push_back(when[_i][_j]);
	}
	sort(all(times));
	for(int i : {0, 2}){
		if(!flag) st.add(times[i], times[i + 1] - 1, k);
		else if(times[i] < times[i + 1]){
			init[times[i]]++;
			if(times[i + 1] < H * W) init[times[i + 1]]--;
		}
	}
}
void give_initial_chart(int h, int w, vector<int> r, vector<int> c){
	H = h; W = w;
	R = r; C = c;
	when.assign(H + 2, vector<int>(W + 2, H * W));
	init.resize(H * W);
	for(int i = 0; i < H * W; i++){
		R[i]++; C[i]++;
		when[R[i]][C[i]] = i;
	}
	for(int i = 0; i <= H; i++){
		for(int j = 0; j <= W; j++){
			add_contribution(i, j, 1, true);
		}
	}
	for(int i = 1; i < H * W; i++) init[i] += init[i - 1];
	st = segtree(init);
}

int swap_seats(int a, int b) {
	set<pair<int, int>> changes;
	int u = R[a], v = C[a];
	for(int i : {u - 1, u})
		for(int j : {v - 1, v})
			changes.insert({i, j});
	u = R[b], v = C[b];

	for(int i : {u - 1, u})
		for(int j : {v - 1, v})
			changes.insert({i, j});
	for(auto it : changes) add_contribution(it.first, it.second, -1);
	when[R[b]][C[b]] = a;
	when[R[a]][C[a]] = b;
	swap(R[a], R[b]);
	swap(C[a], C[b]);
	for(auto it : changes) add_contribution(it.first, it.second, 1);
	Data D = st.tree[1];
	assert(D.mn == 4);
	return D.mncnt;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 412 KB Output is correct
2 Correct 37 ms 540 KB Output is correct
3 Correct 61 ms 552 KB Output is correct
4 Correct 49 ms 404 KB Output is correct
5 Correct 33 ms 420 KB Output is correct
6 Correct 49 ms 396 KB Output is correct
7 Correct 52 ms 428 KB Output is correct
8 Correct 46 ms 416 KB Output is correct
9 Correct 47 ms 408 KB Output is correct
10 Correct 51 ms 400 KB Output is correct
11 Correct 49 ms 452 KB Output is correct
12 Correct 33 ms 412 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 412 KB Output is correct
2 Correct 37 ms 540 KB Output is correct
3 Correct 61 ms 552 KB Output is correct
4 Correct 49 ms 404 KB Output is correct
5 Correct 33 ms 420 KB Output is correct
6 Correct 49 ms 396 KB Output is correct
7 Correct 52 ms 428 KB Output is correct
8 Correct 46 ms 416 KB Output is correct
9 Correct 47 ms 408 KB Output is correct
10 Correct 51 ms 400 KB Output is correct
11 Correct 49 ms 452 KB Output is correct
12 Correct 33 ms 412 KB Output is correct
13 Correct 120 ms 1344 KB Output is correct
14 Correct 129 ms 1332 KB Output is correct
15 Correct 86 ms 1408 KB Output is correct
16 Correct 59 ms 1860 KB Output is correct
17 Correct 110 ms 1356 KB Output is correct
18 Correct 86 ms 1332 KB Output is correct
19 Correct 81 ms 1384 KB Output is correct
20 Correct 71 ms 1504 KB Output is correct
21 Correct 64 ms 1416 KB Output is correct
22 Correct 60 ms 1848 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 855 ms 98472 KB Output is correct
2 Correct 712 ms 98468 KB Output is correct
3 Correct 630 ms 98500 KB Output is correct
4 Correct 697 ms 98460 KB Output is correct
5 Correct 672 ms 98532 KB Output is correct
6 Correct 735 ms 98460 KB Output is correct
7 Correct 728 ms 98464 KB Output is correct
8 Correct 682 ms 98460 KB Output is correct
9 Correct 662 ms 98480 KB Output is correct
10 Correct 625 ms 98460 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 1360 KB Output is correct
2 Correct 165 ms 9036 KB Output is correct
3 Correct 636 ms 98436 KB Output is correct
4 Correct 842 ms 98460 KB Output is correct
5 Correct 712 ms 106360 KB Output is correct
6 Correct 1201 ms 149276 KB Output is correct
7 Correct 678 ms 101036 KB Output is correct
8 Correct 686 ms 98592 KB Output is correct
9 Correct 745 ms 98848 KB Output is correct
10 Correct 731 ms 103112 KB Output is correct
11 Correct 753 ms 121888 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 1904 KB Output is correct
2 Correct 262 ms 1964 KB Output is correct
3 Correct 343 ms 1924 KB Output is correct
4 Correct 423 ms 2016 KB Output is correct
5 Correct 771 ms 2852 KB Output is correct
6 Correct 1740 ms 107224 KB Output is correct
7 Correct 1664 ms 107204 KB Output is correct
8 Correct 1506 ms 107220 KB Output is correct
9 Correct 1985 ms 107224 KB Output is correct
10 Correct 1470 ms 107224 KB Output is correct
11 Correct 1519 ms 107220 KB Output is correct
12 Correct 1355 ms 107240 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 412 KB Output is correct
2 Correct 37 ms 540 KB Output is correct
3 Correct 61 ms 552 KB Output is correct
4 Correct 49 ms 404 KB Output is correct
5 Correct 33 ms 420 KB Output is correct
6 Correct 49 ms 396 KB Output is correct
7 Correct 52 ms 428 KB Output is correct
8 Correct 46 ms 416 KB Output is correct
9 Correct 47 ms 408 KB Output is correct
10 Correct 51 ms 400 KB Output is correct
11 Correct 49 ms 452 KB Output is correct
12 Correct 33 ms 412 KB Output is correct
13 Correct 120 ms 1344 KB Output is correct
14 Correct 129 ms 1332 KB Output is correct
15 Correct 86 ms 1408 KB Output is correct
16 Correct 59 ms 1860 KB Output is correct
17 Correct 110 ms 1356 KB Output is correct
18 Correct 86 ms 1332 KB Output is correct
19 Correct 81 ms 1384 KB Output is correct
20 Correct 71 ms 1504 KB Output is correct
21 Correct 64 ms 1416 KB Output is correct
22 Correct 60 ms 1848 KB Output is correct
23 Correct 855 ms 98472 KB Output is correct
24 Correct 712 ms 98468 KB Output is correct
25 Correct 630 ms 98500 KB Output is correct
26 Correct 697 ms 98460 KB Output is correct
27 Correct 672 ms 98532 KB Output is correct
28 Correct 735 ms 98460 KB Output is correct
29 Correct 728 ms 98464 KB Output is correct
30 Correct 682 ms 98460 KB Output is correct
31 Correct 662 ms 98480 KB Output is correct
32 Correct 625 ms 98460 KB Output is correct
33 Correct 112 ms 1360 KB Output is correct
34 Correct 165 ms 9036 KB Output is correct
35 Correct 636 ms 98436 KB Output is correct
36 Correct 842 ms 98460 KB Output is correct
37 Correct 712 ms 106360 KB Output is correct
38 Correct 1201 ms 149276 KB Output is correct
39 Correct 678 ms 101036 KB Output is correct
40 Correct 686 ms 98592 KB Output is correct
41 Correct 745 ms 98848 KB Output is correct
42 Correct 731 ms 103112 KB Output is correct
43 Correct 753 ms 121888 KB Output is correct
44 Correct 182 ms 1904 KB Output is correct
45 Correct 262 ms 1964 KB Output is correct
46 Correct 343 ms 1924 KB Output is correct
47 Correct 423 ms 2016 KB Output is correct
48 Correct 771 ms 2852 KB Output is correct
49 Correct 1740 ms 107224 KB Output is correct
50 Correct 1664 ms 107204 KB Output is correct
51 Correct 1506 ms 107220 KB Output is correct
52 Correct 1985 ms 107224 KB Output is correct
53 Correct 1470 ms 107224 KB Output is correct
54 Correct 1519 ms 107220 KB Output is correct
55 Correct 1355 ms 107240 KB Output is correct
56 Correct 293 ms 2116 KB Output is correct
57 Correct 629 ms 1944 KB Output is correct
58 Correct 865 ms 2820 KB Output is correct
59 Correct 2223 ms 99492 KB Output is correct
60 Correct 2999 ms 99424 KB Output is correct
61 Correct 1790 ms 99484 KB Output is correct
62 Correct 1629 ms 103404 KB Output is correct
63 Correct 2589 ms 101988 KB Output is correct
64 Correct 2066 ms 100284 KB Output is correct
65 Correct 1697 ms 99556 KB Output is correct
66 Correct 2114 ms 99768 KB Output is correct
67 Correct 1949 ms 104092 KB Output is correct
68 Correct 1696 ms 113892 KB Output is correct
69 Correct 2621 ms 122860 KB Output is correct