Submission #826728

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
826728	2023-08-15T23:39:22 Z	NK_	Diversity (CEOI21_diversity)	C++17	64 / 100	308 ms	39104 KB

diversity

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using vi = V<int>;
using ll = long long;
using pi = pair<int, int>;
using vpi = V<pi>;
using vl = V<ll>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
 	
	int N, Q; cin >> N >> Q;
	vi A(N); for(auto& x : A) cin >> x;
	assert(Q == 1);
	int l, r; cin >> l >> r;
	assert(l == 1 && r == N);

	unordered_map<int, int> F; for(auto& x : A) F[x]++;

	vpi B; for(auto& x : F) B.pb(mp(x.s, x.f));
	sort(begin(B), end(B));

	vpi L, R;
	for(int i = 0; i < sz(B); i += 2) L.pb(B[i]);
	for(int i = 1; i < sz(B); i += 2) R.pb(B[i]);
	reverse(begin(R), end(R));
	
	vpi ord; 
	for(auto& x : L) ord.pb(x);
	for(auto& x : R) ord.pb(x);

	unordered_map<int, int> ORD; for(int i = 0; i < sz(ord); i++) ORD[ord[i].s] = i;

	sort(begin(A), end(A), [&](int x, int y) {
		if (ORD[x] == ORD[y]) return x < y;
		return ORD[x] < ORD[y];
	});

	ll ans = 0;
	unordered_map<int, int> lst;
	for(int i = 0; i < N; i++) {
		int LST = (lst.find(A[i]) == lst.end() ? -1 : lst[A[i]]);
		ans += (i - LST) * 1LL * (N - i);
		lst[A[i]] = i;
	}
	cout << ans << nl;

	exit(0-0);
}

Subtask #1
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	3 ms	340 KB	Output is correct
4	Correct	27 ms	732 KB	Output is correct
5	Correct	55 ms	1108 KB	Output is correct
6	Correct	85 ms	1492 KB	Output is correct
7	Correct	80 ms	1492 KB	Output is correct
8	Correct	85 ms	1492 KB	Output is correct
9	Correct	84 ms	1492 KB	Output is correct
10	Correct	84 ms	1492 KB	Output is correct
11	Correct	84 ms	1492 KB	Output is correct
12	Correct	84 ms	1492 KB	Output is correct
13	Correct	86 ms	1492 KB	Output is correct
14	Correct	84 ms	1492 KB	Output is correct
15	Correct	89 ms	1492 KB	Output is correct

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	3 ms	340 KB	Output is correct
4	Correct	27 ms	732 KB	Output is correct
5	Correct	55 ms	1108 KB	Output is correct
6	Correct	85 ms	1492 KB	Output is correct
7	Correct	80 ms	1492 KB	Output is correct
8	Correct	85 ms	1492 KB	Output is correct
9	Correct	84 ms	1492 KB	Output is correct
10	Correct	84 ms	1492 KB	Output is correct
11	Correct	84 ms	1492 KB	Output is correct
12	Correct	84 ms	1492 KB	Output is correct
13	Correct	86 ms	1492 KB	Output is correct
14	Correct	84 ms	1492 KB	Output is correct
15	Correct	89 ms	1492 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	3 ms	340 KB	Output is correct
19	Correct	28 ms	724 KB	Output is correct
20	Correct	59 ms	1108 KB	Output is correct
21	Correct	89 ms	1504 KB	Output is correct
22	Correct	89 ms	1492 KB	Output is correct
23	Correct	89 ms	1504 KB	Output is correct
24	Correct	89 ms	1504 KB	Output is correct
25	Correct	100 ms	1508 KB	Output is correct
26	Correct	91 ms	1508 KB	Output is correct
27	Correct	89 ms	1492 KB	Output is correct
28	Correct	94 ms	1492 KB	Output is correct
29	Correct	90 ms	1492 KB	Output is correct
30	Correct	97 ms	1492 KB	Output is correct

Subtask #4
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	3 ms	340 KB	Output is correct
4	Correct	27 ms	732 KB	Output is correct
5	Correct	55 ms	1108 KB	Output is correct
6	Correct	85 ms	1492 KB	Output is correct
7	Correct	80 ms	1492 KB	Output is correct
8	Correct	85 ms	1492 KB	Output is correct
9	Correct	84 ms	1492 KB	Output is correct
10	Correct	84 ms	1492 KB	Output is correct
11	Correct	84 ms	1492 KB	Output is correct
12	Correct	84 ms	1492 KB	Output is correct
13	Correct	86 ms	1492 KB	Output is correct
14	Correct	84 ms	1492 KB	Output is correct
15	Correct	89 ms	1492 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	3 ms	340 KB	Output is correct
19	Correct	28 ms	724 KB	Output is correct
20	Correct	59 ms	1108 KB	Output is correct
21	Correct	89 ms	1504 KB	Output is correct
22	Correct	89 ms	1492 KB	Output is correct
23	Correct	89 ms	1504 KB	Output is correct
24	Correct	89 ms	1504 KB	Output is correct
25	Correct	100 ms	1508 KB	Output is correct
26	Correct	91 ms	1508 KB	Output is correct
27	Correct	89 ms	1492 KB	Output is correct
28	Correct	94 ms	1492 KB	Output is correct
29	Correct	90 ms	1492 KB	Output is correct
30	Correct	97 ms	1492 KB	Output is correct
31	Correct	1 ms	212 KB	Output is correct
32	Correct	1 ms	340 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	3 ms	340 KB	Output is correct
35	Correct	6 ms	380 KB	Output is correct
36	Correct	4 ms	468 KB	Output is correct
37	Correct	19 ms	584 KB	Output is correct
38	Correct	28 ms	636 KB	Output is correct
39	Correct	39 ms	824 KB	Output is correct
40	Correct	85 ms	1232 KB	Output is correct
41	Correct	124 ms	1596 KB	Output is correct
42	Correct	119 ms	1596 KB	Output is correct
43	Correct	122 ms	1588 KB	Output is correct
44	Correct	119 ms	1608 KB	Output is correct
45	Correct	125 ms	1592 KB	Output is correct
46	Correct	119 ms	1592 KB	Output is correct
47	Correct	138 ms	1588 KB	Output is correct
48	Correct	121 ms	1592 KB	Output is correct
49	Correct	123 ms	1612 KB	Output is correct
50	Correct	123 ms	1624 KB	Output is correct
51	Correct	138 ms	1588 KB	Output is correct
52	Correct	120 ms	1632 KB	Output is correct
53	Correct	121 ms	1668 KB	Output is correct
54	Correct	121 ms	1596 KB	Output is correct
55	Correct	121 ms	1592 KB	Output is correct
56	Correct	122 ms	1588 KB	Output is correct
57	Correct	123 ms	1596 KB	Output is correct
58	Correct	121 ms	1604 KB	Output is correct
59	Correct	124 ms	1600 KB	Output is correct
60	Correct	136 ms	1624 KB	Output is correct

Subtask #5
26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	3 ms	340 KB	Output is correct
14	Correct	27 ms	732 KB	Output is correct
15	Correct	55 ms	1108 KB	Output is correct
16	Correct	85 ms	1492 KB	Output is correct
17	Correct	80 ms	1492 KB	Output is correct
18	Correct	85 ms	1492 KB	Output is correct
19	Correct	84 ms	1492 KB	Output is correct
20	Correct	84 ms	1492 KB	Output is correct
21	Correct	84 ms	1492 KB	Output is correct
22	Correct	84 ms	1492 KB	Output is correct
23	Correct	86 ms	1492 KB	Output is correct
24	Correct	84 ms	1492 KB	Output is correct
25	Correct	89 ms	1492 KB	Output is correct
26	Correct	1 ms	212 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	3 ms	340 KB	Output is correct
29	Correct	28 ms	724 KB	Output is correct
30	Correct	59 ms	1108 KB	Output is correct
31	Correct	89 ms	1504 KB	Output is correct
32	Correct	89 ms	1492 KB	Output is correct
33	Correct	89 ms	1504 KB	Output is correct
34	Correct	89 ms	1504 KB	Output is correct
35	Correct	100 ms	1508 KB	Output is correct
36	Correct	91 ms	1508 KB	Output is correct
37	Correct	89 ms	1492 KB	Output is correct
38	Correct	94 ms	1492 KB	Output is correct
39	Correct	90 ms	1492 KB	Output is correct
40	Correct	97 ms	1492 KB	Output is correct
41	Correct	1 ms	212 KB	Output is correct
42	Correct	1 ms	340 KB	Output is correct
43	Correct	1 ms	340 KB	Output is correct
44	Correct	3 ms	340 KB	Output is correct
45	Correct	6 ms	380 KB	Output is correct
46	Correct	4 ms	468 KB	Output is correct
47	Correct	19 ms	584 KB	Output is correct
48	Correct	28 ms	636 KB	Output is correct
49	Correct	39 ms	824 KB	Output is correct
50	Correct	85 ms	1232 KB	Output is correct
51	Correct	124 ms	1596 KB	Output is correct
52	Correct	119 ms	1596 KB	Output is correct
53	Correct	122 ms	1588 KB	Output is correct
54	Correct	119 ms	1608 KB	Output is correct
55	Correct	125 ms	1592 KB	Output is correct
56	Correct	119 ms	1592 KB	Output is correct
57	Correct	138 ms	1588 KB	Output is correct
58	Correct	121 ms	1592 KB	Output is correct
59	Correct	123 ms	1612 KB	Output is correct
60	Correct	123 ms	1624 KB	Output is correct
61	Correct	138 ms	1588 KB	Output is correct
62	Correct	120 ms	1632 KB	Output is correct
63	Correct	121 ms	1668 KB	Output is correct
64	Correct	121 ms	1596 KB	Output is correct
65	Correct	121 ms	1592 KB	Output is correct
66	Correct	122 ms	1588 KB	Output is correct
67	Correct	123 ms	1596 KB	Output is correct
68	Correct	121 ms	1604 KB	Output is correct
69	Correct	124 ms	1600 KB	Output is correct
70	Correct	136 ms	1624 KB	Output is correct
71	Correct	22 ms	740 KB	Output is correct
72	Correct	21 ms	744 KB	Output is correct
73	Correct	27 ms	744 KB	Output is correct
74	Correct	30 ms	736 KB	Output is correct
75	Correct	27 ms	744 KB	Output is correct
76	Correct	46 ms	1376 KB	Output is correct
77	Correct	46 ms	1356 KB	Output is correct
78	Correct	46 ms	1360 KB	Output is correct
79	Correct	71 ms	1360 KB	Output is correct
80	Correct	46 ms	1388 KB	Output is correct
81	Correct	99 ms	2540 KB	Output is correct
82	Correct	103 ms	2544 KB	Output is correct
83	Correct	98 ms	2540 KB	Output is correct
84	Correct	110 ms	2544 KB	Output is correct
85	Correct	99 ms	2532 KB	Output is correct
86	Correct	121 ms	3928 KB	Output is correct
87	Correct	114 ms	4048 KB	Output is correct
88	Correct	111 ms	3932 KB	Output is correct
89	Correct	107 ms	3912 KB	Output is correct
90	Correct	111 ms	3944 KB	Output is correct
91	Correct	241 ms	17632 KB	Output is correct
92	Correct	220 ms	17624 KB	Output is correct
93	Correct	220 ms	17528 KB	Output is correct
94	Correct	240 ms	17628 KB	Output is correct
95	Correct	235 ms	17624 KB	Output is correct
96	Correct	271 ms	33976 KB	Output is correct
97	Correct	283 ms	33928 KB	Output is correct
98	Correct	263 ms	33980 KB	Output is correct
99	Correct	266 ms	33960 KB	Output is correct
100	Correct	281 ms	33924 KB	Output is correct
101	Correct	287 ms	33948 KB	Output is correct
102	Correct	271 ms	33920 KB	Output is correct
103	Correct	265 ms	33924 KB	Output is correct
104	Correct	265 ms	33948 KB	Output is correct
105	Correct	281 ms	33928 KB	Output is correct
106	Correct	284 ms	39048 KB	Output is correct
107	Correct	308 ms	39068 KB	Output is correct
108	Correct	296 ms	39036 KB	Output is correct
109	Correct	302 ms	39104 KB	Output is correct
110	Correct	298 ms	39072 KB	Output is correct
111	Correct	288 ms	39104 KB	Output is correct
112	Correct	285 ms	39032 KB	Output is correct
113	Correct	293 ms	39032 KB	Output is correct
114	Correct	285 ms	39060 KB	Output is correct
115	Correct	299 ms	39088 KB	Output is correct

Subtask #6
0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	3 ms	340 KB	Output is correct
14	Correct	27 ms	732 KB	Output is correct
15	Correct	55 ms	1108 KB	Output is correct
16	Correct	85 ms	1492 KB	Output is correct
17	Correct	80 ms	1492 KB	Output is correct
18	Correct	85 ms	1492 KB	Output is correct
19	Correct	84 ms	1492 KB	Output is correct
20	Correct	84 ms	1492 KB	Output is correct
21	Correct	84 ms	1492 KB	Output is correct
22	Correct	84 ms	1492 KB	Output is correct
23	Correct	86 ms	1492 KB	Output is correct
24	Correct	84 ms	1492 KB	Output is correct
25	Correct	89 ms	1492 KB	Output is correct
26	Correct	1 ms	212 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	3 ms	340 KB	Output is correct
29	Correct	28 ms	724 KB	Output is correct
30	Correct	59 ms	1108 KB	Output is correct
31	Correct	89 ms	1504 KB	Output is correct
32	Correct	89 ms	1492 KB	Output is correct
33	Correct	89 ms	1504 KB	Output is correct
34	Correct	89 ms	1504 KB	Output is correct
35	Correct	100 ms	1508 KB	Output is correct
36	Correct	91 ms	1508 KB	Output is correct
37	Correct	89 ms	1492 KB	Output is correct
38	Correct	94 ms	1492 KB	Output is correct
39	Correct	90 ms	1492 KB	Output is correct
40	Correct	97 ms	1492 KB	Output is correct
41	Correct	1 ms	212 KB	Output is correct
42	Correct	1 ms	340 KB	Output is correct
43	Correct	1 ms	340 KB	Output is correct
44	Correct	3 ms	340 KB	Output is correct
45	Correct	6 ms	380 KB	Output is correct
46	Correct	4 ms	468 KB	Output is correct
47	Correct	19 ms	584 KB	Output is correct
48	Correct	28 ms	636 KB	Output is correct
49	Correct	39 ms	824 KB	Output is correct
50	Correct	85 ms	1232 KB	Output is correct
51	Correct	124 ms	1596 KB	Output is correct
52	Correct	119 ms	1596 KB	Output is correct
53	Correct	122 ms	1588 KB	Output is correct
54	Correct	119 ms	1608 KB	Output is correct
55	Correct	125 ms	1592 KB	Output is correct
56	Correct	119 ms	1592 KB	Output is correct
57	Correct	138 ms	1588 KB	Output is correct
58	Correct	121 ms	1592 KB	Output is correct
59	Correct	123 ms	1612 KB	Output is correct
60	Correct	123 ms	1624 KB	Output is correct
61	Correct	138 ms	1588 KB	Output is correct
62	Correct	120 ms	1632 KB	Output is correct
63	Correct	121 ms	1668 KB	Output is correct
64	Correct	121 ms	1596 KB	Output is correct
65	Correct	121 ms	1592 KB	Output is correct
66	Correct	122 ms	1588 KB	Output is correct
67	Correct	123 ms	1596 KB	Output is correct
68	Correct	121 ms	1604 KB	Output is correct
69	Correct	124 ms	1600 KB	Output is correct
70	Correct	136 ms	1624 KB	Output is correct
71	Correct	22 ms	740 KB	Output is correct
72	Correct	21 ms	744 KB	Output is correct
73	Correct	27 ms	744 KB	Output is correct
74	Correct	30 ms	736 KB	Output is correct
75	Correct	27 ms	744 KB	Output is correct
76	Correct	46 ms	1376 KB	Output is correct
77	Correct	46 ms	1356 KB	Output is correct
78	Correct	46 ms	1360 KB	Output is correct
79	Correct	71 ms	1360 KB	Output is correct
80	Correct	46 ms	1388 KB	Output is correct
81	Correct	99 ms	2540 KB	Output is correct
82	Correct	103 ms	2544 KB	Output is correct
83	Correct	98 ms	2540 KB	Output is correct
84	Correct	110 ms	2544 KB	Output is correct
85	Correct	99 ms	2532 KB	Output is correct
86	Correct	121 ms	3928 KB	Output is correct
87	Correct	114 ms	4048 KB	Output is correct
88	Correct	111 ms	3932 KB	Output is correct
89	Correct	107 ms	3912 KB	Output is correct
90	Correct	111 ms	3944 KB	Output is correct
91	Correct	241 ms	17632 KB	Output is correct
92	Correct	220 ms	17624 KB	Output is correct
93	Correct	220 ms	17528 KB	Output is correct
94	Correct	240 ms	17628 KB	Output is correct
95	Correct	235 ms	17624 KB	Output is correct
96	Correct	271 ms	33976 KB	Output is correct
97	Correct	283 ms	33928 KB	Output is correct
98	Correct	263 ms	33980 KB	Output is correct
99	Correct	266 ms	33960 KB	Output is correct
100	Correct	281 ms	33924 KB	Output is correct
101	Correct	287 ms	33948 KB	Output is correct
102	Correct	271 ms	33920 KB	Output is correct
103	Correct	265 ms	33924 KB	Output is correct
104	Correct	265 ms	33948 KB	Output is correct
105	Correct	281 ms	33928 KB	Output is correct
106	Correct	284 ms	39048 KB	Output is correct
107	Correct	308 ms	39068 KB	Output is correct
108	Correct	296 ms	39036 KB	Output is correct
109	Correct	302 ms	39104 KB	Output is correct
110	Correct	298 ms	39072 KB	Output is correct
111	Correct	288 ms	39104 KB	Output is correct
112	Correct	285 ms	39032 KB	Output is correct
113	Correct	293 ms	39032 KB	Output is correct
114	Correct	285 ms	39060 KB	Output is correct
115	Correct	299 ms	39088 KB	Output is correct
116	Runtime error	1 ms	468 KB	Execution killed with signal 6
117	Halted	0 ms	0 KB	-

Submission #826728

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 10.0 / 10.0

Subtask #3 8.0 / 8.0

Subtask #4 16.0 / 16.0

Subtask #5 26.0 / 26.0

Subtask #6 0 / 36.0

Subtask #1
4.0 / 4.0

Subtask #2
10.0 / 10.0

Subtask #3
8.0 / 8.0

Subtask #4
16.0 / 16.0

Subtask #5
26.0 / 26.0

Subtask #6
0 / 36.0