oj.uz

Submission #670203

# Submission time Handle Problem Language Result Execution time Memory
670203 2022-12-08T09:40:31 Z ymm Rope (JOI17_rope) C++17
80 / 100
 2500 ms 120184 KB 
///
///   ♪ Hashire sori yo ♪
///   ♪ Kaze no you ni  ♪
///   ♪ Tsukimihara wo  ♪
///   ♪ PADORU PADORU   ♪
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 1<<20;
int a[N];
vector<pii> vec[N];
int n, m;

int cnt[N];
set<pii, greater<pii>> cnts;
vector<pii> record;
bool recording;

void add(int c, int x)
{
	if (recording)
		record.push_back({c, cnt[c]});
	cnts.erase({cnt[c], c});
	cnt[c] += x;
	cnts.insert({cnt[c], c});
}

void revert()
{
	recording = 0;
	while (record.size()) {
		auto [c, x] = record.back();
		record.pop_back();
		add(c, x-cnt[c]);
	}
}

int count(int c, bool odd)
{
	recording = 1;
	int cntc = cnt[c];
	int ans = 0;
	add(c, -cntc);
	vector<pair<pii,bool>> v;
	int lst = 0;
	for (auto [l, r] : vec[c]) {
		if (lst != l)
			v.push_back({{lst, l}, 0});
		v.push_back({{l, r}, 1});
		lst = r;
	}
	if (lst != n)
		v.push_back({{lst, n}, 0});
	for (auto [lr, is] : v) {
		auto [l, r] = lr;
		if (r == n)
			break;
		odd ^= (r - l) & 1;
		if (odd) {
			++cntc;
			++ans;
			add(a[r - 1 + is], -1);
		}
	}
	ans += n - cntc - cnts.begin()->first;
	revert();
	return ans;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	Loop (i,0,n) {
		cin >> a[i];
		--a[i];
	}
	int lst = 0;
	Loop (i,0,n) {
		if (a[i] != a[lst]) {
			vec[a[lst]].push_back({lst, i});
			lst = i;
		}
		add(a[i], 1);
	}
	vec[a[lst]].push_back({lst, n});
	Loop (i,0,m) {
		int ans = min(count(i, 0), count(i, 1));
		cout << ans << '\n';
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24916 KB Output is correct
2 Correct 13 ms 24956 KB Output is correct
3 Correct 14 ms 24872 KB Output is correct
4 Correct 13 ms 24916 KB Output is correct
5 Correct 13 ms 24916 KB Output is correct
6 Correct 13 ms 24916 KB Output is correct
7 Correct 13 ms 24928 KB Output is correct
8 Correct 13 ms 24848 KB Output is correct
9 Correct 14 ms 24916 KB Output is correct
10 Correct 14 ms 24920 KB Output is correct
11 Correct 13 ms 24916 KB Output is correct
12 Correct 13 ms 24916 KB Output is correct
13 Correct 14 ms 24868 KB Output is correct
14 Correct 13 ms 24960 KB Output is correct
15 Correct 13 ms 24956 KB Output is correct
16 Correct 13 ms 24916 KB Output is correct
17 Correct 13 ms 24916 KB Output is correct
18 Correct 14 ms 24956 KB Output is correct
19 Correct 13 ms 24856 KB Output is correct
20 Correct 14 ms 24884 KB Output is correct
21 Correct 12 ms 24916 KB Output is correct
22 Correct 14 ms 24916 KB Output is correct
23 Correct 13 ms 24964 KB Output is correct
24 Correct 13 ms 24852 KB Output is correct
25 Correct 13 ms 24916 KB Output is correct
26 Correct 13 ms 24916 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24916 KB Output is correct
2 Correct 13 ms 24956 KB Output is correct
3 Correct 14 ms 24872 KB Output is correct
4 Correct 13 ms 24916 KB Output is correct
5 Correct 13 ms 24916 KB Output is correct
6 Correct 13 ms 24916 KB Output is correct
7 Correct 13 ms 24928 KB Output is correct
8 Correct 13 ms 24848 KB Output is correct
9 Correct 14 ms 24916 KB Output is correct
10 Correct 14 ms 24920 KB Output is correct
11 Correct 13 ms 24916 KB Output is correct
12 Correct 13 ms 24916 KB Output is correct
13 Correct 14 ms 24868 KB Output is correct
14 Correct 13 ms 24960 KB Output is correct
15 Correct 13 ms 24956 KB Output is correct
16 Correct 13 ms 24916 KB Output is correct
17 Correct 13 ms 24916 KB Output is correct
18 Correct 14 ms 24956 KB Output is correct
19 Correct 13 ms 24856 KB Output is correct
20 Correct 14 ms 24884 KB Output is correct
21 Correct 12 ms 24916 KB Output is correct
22 Correct 14 ms 24916 KB Output is correct
23 Correct 13 ms 24964 KB Output is correct
24 Correct 13 ms 24852 KB Output is correct
25 Correct 13 ms 24916 KB Output is correct
26 Correct 13 ms 24916 KB Output is correct
27 Correct 65 ms 27324 KB Output is correct
28 Correct 47 ms 27620 KB Output is correct
29 Correct 61 ms 27100 KB Output is correct
30 Correct 51 ms 27168 KB Output is correct
31 Correct 63 ms 27228 KB Output is correct
32 Correct 49 ms 27456 KB Output is correct
33 Correct 64 ms 27288 KB Output is correct
34 Correct 52 ms 27116 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24916 KB Output is correct
2 Correct 13 ms 24956 KB Output is correct
3 Correct 14 ms 24872 KB Output is correct
4 Correct 13 ms 24916 KB Output is correct
5 Correct 13 ms 24916 KB Output is correct
6 Correct 13 ms 24916 KB Output is correct
7 Correct 13 ms 24928 KB Output is correct
8 Correct 13 ms 24848 KB Output is correct
9 Correct 14 ms 24916 KB Output is correct
10 Correct 14 ms 24920 KB Output is correct
11 Correct 13 ms 24916 KB Output is correct
12 Correct 13 ms 24916 KB Output is correct
13 Correct 14 ms 24868 KB Output is correct
14 Correct 13 ms 24960 KB Output is correct
15 Correct 13 ms 24956 KB Output is correct
16 Correct 13 ms 24916 KB Output is correct
17 Correct 13 ms 24916 KB Output is correct
18 Correct 14 ms 24956 KB Output is correct
19 Correct 13 ms 24856 KB Output is correct
20 Correct 14 ms 24884 KB Output is correct
21 Correct 12 ms 24916 KB Output is correct
22 Correct 14 ms 24916 KB Output is correct
23 Correct 13 ms 24964 KB Output is correct
24 Correct 13 ms 24852 KB Output is correct
25 Correct 13 ms 24916 KB Output is correct
26 Correct 13 ms 24916 KB Output is correct
27 Correct 65 ms 27324 KB Output is correct
28 Correct 47 ms 27620 KB Output is correct
29 Correct 61 ms 27100 KB Output is correct
30 Correct 51 ms 27168 KB Output is correct
31 Correct 63 ms 27228 KB Output is correct
32 Correct 49 ms 27456 KB Output is correct
33 Correct 64 ms 27288 KB Output is correct
34 Correct 52 ms 27116 KB Output is correct
35 Correct 138 ms 26816 KB Output is correct
36 Correct 138 ms 26912 KB Output is correct
37 Correct 141 ms 26824 KB Output is correct
38 Correct 139 ms 26792 KB Output is correct
39 Correct 137 ms 26884 KB Output is correct
40 Correct 124 ms 27092 KB Output is correct
41 Correct 127 ms 27100 KB Output is correct
42 Correct 118 ms 27036 KB Output is correct
43 Correct 117 ms 27084 KB Output is correct
44 Correct 131 ms 27072 KB Output is correct
45 Correct 125 ms 27088 KB Output is correct
46 Correct 119 ms 27008 KB Output is correct
47 Correct 121 ms 27012 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24916 KB Output is correct
2 Correct 13 ms 24956 KB Output is correct
3 Correct 14 ms 24872 KB Output is correct
4 Correct 13 ms 24916 KB Output is correct
5 Correct 13 ms 24916 KB Output is correct
6 Correct 13 ms 24916 KB Output is correct
7 Correct 13 ms 24928 KB Output is correct
8 Correct 13 ms 24848 KB Output is correct
9 Correct 14 ms 24916 KB Output is correct
10 Correct 14 ms 24920 KB Output is correct
11 Correct 13 ms 24916 KB Output is correct
12 Correct 13 ms 24916 KB Output is correct
13 Correct 14 ms 24868 KB Output is correct
14 Correct 13 ms 24960 KB Output is correct
15 Correct 13 ms 24956 KB Output is correct
16 Correct 13 ms 24916 KB Output is correct
17 Correct 13 ms 24916 KB Output is correct
18 Correct 14 ms 24956 KB Output is correct
19 Correct 13 ms 24856 KB Output is correct
20 Correct 14 ms 24884 KB Output is correct
21 Correct 12 ms 24916 KB Output is correct
22 Correct 14 ms 24916 KB Output is correct
23 Correct 13 ms 24964 KB Output is correct
24 Correct 13 ms 24852 KB Output is correct
25 Correct 13 ms 24916 KB Output is correct
26 Correct 13 ms 24916 KB Output is correct
27 Correct 65 ms 27324 KB Output is correct
28 Correct 47 ms 27620 KB Output is correct
29 Correct 61 ms 27100 KB Output is correct
30 Correct 51 ms 27168 KB Output is correct
31 Correct 63 ms 27228 KB Output is correct
32 Correct 49 ms 27456 KB Output is correct
33 Correct 64 ms 27288 KB Output is correct
34 Correct 52 ms 27116 KB Output is correct
35 Correct 138 ms 26816 KB Output is correct
36 Correct 138 ms 26912 KB Output is correct
37 Correct 141 ms 26824 KB Output is correct
38 Correct 139 ms 26792 KB Output is correct
39 Correct 137 ms 26884 KB Output is correct
40 Correct 124 ms 27092 KB Output is correct
41 Correct 127 ms 27100 KB Output is correct
42 Correct 118 ms 27036 KB Output is correct
43 Correct 117 ms 27084 KB Output is correct
44 Correct 131 ms 27072 KB Output is correct
45 Correct 125 ms 27088 KB Output is correct
46 Correct 119 ms 27008 KB Output is correct
47 Correct 121 ms 27012 KB Output is correct
48 Correct 1653 ms 47060 KB Output is correct
49 Correct 1663 ms 46924 KB Output is correct
50 Correct 1647 ms 46908 KB Output is correct
51 Correct 1505 ms 46444 KB Output is correct
52 Correct 1419 ms 43444 KB Output is correct
53 Correct 1314 ms 45388 KB Output is correct
54 Correct 1224 ms 43456 KB Output is correct
55 Correct 1195 ms 43084 KB Output is correct
56 Correct 1168 ms 42400 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24916 KB Output is correct
2 Correct 13 ms 24956 KB Output is correct
3 Correct 14 ms 24872 KB Output is correct
4 Correct 13 ms 24916 KB Output is correct
5 Correct 13 ms 24916 KB Output is correct
6 Correct 13 ms 24916 KB Output is correct
7 Correct 13 ms 24928 KB Output is correct
8 Correct 13 ms 24848 KB Output is correct
9 Correct 14 ms 24916 KB Output is correct
10 Correct 14 ms 24920 KB Output is correct
11 Correct 13 ms 24916 KB Output is correct
12 Correct 13 ms 24916 KB Output is correct
13 Correct 14 ms 24868 KB Output is correct
14 Correct 13 ms 24960 KB Output is correct
15 Correct 13 ms 24956 KB Output is correct
16 Correct 13 ms 24916 KB Output is correct
17 Correct 13 ms 24916 KB Output is correct
18 Correct 14 ms 24956 KB Output is correct
19 Correct 13 ms 24856 KB Output is correct
20 Correct 14 ms 24884 KB Output is correct
21 Correct 12 ms 24916 KB Output is correct
22 Correct 14 ms 24916 KB Output is correct
23 Correct 13 ms 24964 KB Output is correct
24 Correct 13 ms 24852 KB Output is correct
25 Correct 13 ms 24916 KB Output is correct
26 Correct 13 ms 24916 KB Output is correct
27 Correct 65 ms 27324 KB Output is correct
28 Correct 47 ms 27620 KB Output is correct
29 Correct 61 ms 27100 KB Output is correct
30 Correct 51 ms 27168 KB Output is correct
31 Correct 63 ms 27228 KB Output is correct
32 Correct 49 ms 27456 KB Output is correct
33 Correct 64 ms 27288 KB Output is correct
34 Correct 52 ms 27116 KB Output is correct
35 Correct 138 ms 26816 KB Output is correct
36 Correct 138 ms 26912 KB Output is correct
37 Correct 141 ms 26824 KB Output is correct
38 Correct 139 ms 26792 KB Output is correct
39 Correct 137 ms 26884 KB Output is correct
40 Correct 124 ms 27092 KB Output is correct
41 Correct 127 ms 27100 KB Output is correct
42 Correct 118 ms 27036 KB Output is correct
43 Correct 117 ms 27084 KB Output is correct
44 Correct 131 ms 27072 KB Output is correct
45 Correct 125 ms 27088 KB Output is correct
46 Correct 119 ms 27008 KB Output is correct
47 Correct 121 ms 27012 KB Output is correct
48 Correct 1653 ms 47060 KB Output is correct
49 Correct 1663 ms 46924 KB Output is correct
50 Correct 1647 ms 46908 KB Output is correct
51 Correct 1505 ms 46444 KB Output is correct
52 Correct 1419 ms 43444 KB Output is correct
53 Correct 1314 ms 45388 KB Output is correct
54 Correct 1224 ms 43456 KB Output is correct
55 Correct 1195 ms 43084 KB Output is correct
56 Correct 1168 ms 42400 KB Output is correct
57 Execution timed out 2558 ms 120184 KB Time limit exceeded
58 Halted 0 ms 0 KB -