Submission #572406

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
572406	2022-06-04T10:39:59 Z	MODDI	Pilot (NOI19_pilot)	C++14	89 / 100	1000 ms	70940 KB

pilot

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int maxn = 1e6 + 5;
ll parent[maxn];
ll sz[maxn];
bool on[maxn];
ll find(int x) {return x == parent[x]?x:parent[x] = find(parent[x]);}
ll rez = 0;
void mrg(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;
    rez -= sz[a] * (sz[a]+1) / 2;
    rez -= sz[b] * (sz[b]+1) / 2;
    sz[a] += sz[b];
    rez += sz[a] * (sz[a]+1) / 2;
    parent[b] = a;
}
vector<ll> G[maxn];
ll ans[maxn];
signed main(){
 	ios::sync_with_stdio(0), cin.tie(0);
	int n, q;
	cin>>n>>q;
	for(int i = 0; i < n; i++){
		parent[i] = i;
		sz[i] = 1;
		int a;
		cin>>a;
		G[a].pb(i);
	}
	for(int i = 1; i <= 1000000; i++){
		for(int x : G[i]){
			++rez;
			on[x] = 1;
			if(x && on[x-1]) mrg(x, x-1);
			if(x != n-1 && on[x+1]) mrg(x, x + 1);
		}
		ans[i] = rez;
	}
	for(int i = 0; i < q; i++){
		int a;
		cin>>a;
		cout<<ans[a]<<endl;
	}
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	31700 KB	Output is correct
2	Correct	19 ms	31572 KB	Output is correct
3	Correct	24 ms	31612 KB	Output is correct
4	Correct	19 ms	31532 KB	Output is correct
5	Correct	20 ms	31532 KB	Output is correct
6	Correct	20 ms	31616 KB	Output is correct
7	Correct	22 ms	31588 KB	Output is correct
8	Correct	19 ms	31580 KB	Output is correct
9	Correct	23 ms	31528 KB	Output is correct
10	Correct	18 ms	31628 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	31700 KB	Output is correct
2	Correct	19 ms	31572 KB	Output is correct
3	Correct	24 ms	31612 KB	Output is correct
4	Correct	19 ms	31532 KB	Output is correct
5	Correct	20 ms	31532 KB	Output is correct
6	Correct	20 ms	31616 KB	Output is correct
7	Correct	22 ms	31588 KB	Output is correct
8	Correct	19 ms	31580 KB	Output is correct
9	Correct	23 ms	31528 KB	Output is correct
10	Correct	18 ms	31628 KB	Output is correct
11	Correct	22 ms	31600 KB	Output is correct
12	Correct	19 ms	31640 KB	Output is correct
13	Correct	18 ms	31532 KB	Output is correct
14	Correct	20 ms	31528 KB	Output is correct
15	Correct	18 ms	31632 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	31700 KB	Output is correct
2	Correct	19 ms	31572 KB	Output is correct
3	Correct	24 ms	31612 KB	Output is correct
4	Correct	19 ms	31532 KB	Output is correct
5	Correct	20 ms	31532 KB	Output is correct
6	Correct	20 ms	31616 KB	Output is correct
7	Correct	22 ms	31588 KB	Output is correct
8	Correct	19 ms	31580 KB	Output is correct
9	Correct	23 ms	31528 KB	Output is correct
10	Correct	18 ms	31628 KB	Output is correct
11	Correct	22 ms	31600 KB	Output is correct
12	Correct	19 ms	31640 KB	Output is correct
13	Correct	18 ms	31532 KB	Output is correct
14	Correct	20 ms	31528 KB	Output is correct
15	Correct	18 ms	31632 KB	Output is correct
16	Correct	22 ms	31520 KB	Output is correct
17	Correct	21 ms	31632 KB	Output is correct
18	Correct	22 ms	31624 KB	Output is correct
19	Correct	20 ms	31632 KB	Output is correct
20	Correct	20 ms	31572 KB	Output is correct

Subtask #4
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	31700 KB	Output is correct
2	Correct	19 ms	31572 KB	Output is correct
3	Correct	24 ms	31612 KB	Output is correct
4	Correct	19 ms	31532 KB	Output is correct
5	Correct	20 ms	31532 KB	Output is correct
6	Correct	20 ms	31616 KB	Output is correct
7	Correct	22 ms	31588 KB	Output is correct
8	Correct	19 ms	31580 KB	Output is correct
9	Correct	23 ms	31528 KB	Output is correct
10	Correct	18 ms	31628 KB	Output is correct
11	Correct	22 ms	31600 KB	Output is correct
12	Correct	19 ms	31640 KB	Output is correct
13	Correct	18 ms	31532 KB	Output is correct
14	Correct	20 ms	31528 KB	Output is correct
15	Correct	18 ms	31632 KB	Output is correct
16	Correct	22 ms	31520 KB	Output is correct
17	Correct	21 ms	31632 KB	Output is correct
18	Correct	22 ms	31624 KB	Output is correct
19	Correct	20 ms	31632 KB	Output is correct
20	Correct	20 ms	31572 KB	Output is correct
21	Correct	19 ms	31604 KB	Output is correct
22	Correct	20 ms	31640 KB	Output is correct
23	Correct	20 ms	31704 KB	Output is correct
24	Correct	19 ms	31640 KB	Output is correct
25	Correct	23 ms	31632 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	35768 KB	Output is correct
2	Correct	59 ms	36612 KB	Output is correct
3	Correct	42 ms	35660 KB	Output is correct
4	Correct	52 ms	36264 KB	Output is correct
5	Correct	40 ms	35508 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	158 ms	37476 KB	Output is correct
2	Correct	179 ms	37756 KB	Output is correct
3	Correct	158 ms	37708 KB	Output is correct
4	Correct	160 ms	37896 KB	Output is correct
5	Correct	161 ms	37656 KB	Output is correct

Subtask #7
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	194 ms	37612 KB	Output is correct
2	Correct	168 ms	37844 KB	Output is correct
3	Correct	179 ms	37740 KB	Output is correct
4	Correct	173 ms	38088 KB	Output is correct
5	Correct	186 ms	37900 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	31700 KB	Output is correct
2	Correct	19 ms	31572 KB	Output is correct
3	Correct	24 ms	31612 KB	Output is correct
4	Correct	19 ms	31532 KB	Output is correct
5	Correct	20 ms	31532 KB	Output is correct
6	Correct	20 ms	31616 KB	Output is correct
7	Correct	22 ms	31588 KB	Output is correct
8	Correct	19 ms	31580 KB	Output is correct
9	Correct	23 ms	31528 KB	Output is correct
10	Correct	18 ms	31628 KB	Output is correct
11	Correct	44 ms	35768 KB	Output is correct
12	Correct	59 ms	36612 KB	Output is correct
13	Correct	42 ms	35660 KB	Output is correct
14	Correct	52 ms	36264 KB	Output is correct
15	Correct	40 ms	35508 KB	Output is correct
16	Correct	64 ms	35540 KB	Output is correct
17	Correct	59 ms	36688 KB	Output is correct
18	Correct	67 ms	36684 KB	Output is correct
19	Correct	57 ms	35508 KB	Output is correct
20	Correct	71 ms	36588 KB	Output is correct
21	Correct	65 ms	35552 KB	Output is correct
22	Correct	49 ms	36428 KB	Output is correct
23	Correct	43 ms	35788 KB	Output is correct
24	Correct	52 ms	36492 KB	Output is correct
25	Correct	54 ms	35728 KB	Output is correct

Subtask #9
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	31700 KB	Output is correct
2	Correct	19 ms	31572 KB	Output is correct
3	Correct	24 ms	31612 KB	Output is correct
4	Correct	19 ms	31532 KB	Output is correct
5	Correct	20 ms	31532 KB	Output is correct
6	Correct	20 ms	31616 KB	Output is correct
7	Correct	22 ms	31588 KB	Output is correct
8	Correct	19 ms	31580 KB	Output is correct
9	Correct	23 ms	31528 KB	Output is correct
10	Correct	18 ms	31628 KB	Output is correct
11	Correct	22 ms	31600 KB	Output is correct
12	Correct	19 ms	31640 KB	Output is correct
13	Correct	18 ms	31532 KB	Output is correct
14	Correct	20 ms	31528 KB	Output is correct
15	Correct	18 ms	31632 KB	Output is correct
16	Correct	22 ms	31520 KB	Output is correct
17	Correct	21 ms	31632 KB	Output is correct
18	Correct	22 ms	31624 KB	Output is correct
19	Correct	20 ms	31632 KB	Output is correct
20	Correct	20 ms	31572 KB	Output is correct
21	Correct	19 ms	31604 KB	Output is correct
22	Correct	20 ms	31640 KB	Output is correct
23	Correct	20 ms	31704 KB	Output is correct
24	Correct	19 ms	31640 KB	Output is correct
25	Correct	23 ms	31632 KB	Output is correct
26	Correct	44 ms	35768 KB	Output is correct
27	Correct	59 ms	36612 KB	Output is correct
28	Correct	42 ms	35660 KB	Output is correct
29	Correct	52 ms	36264 KB	Output is correct
30	Correct	40 ms	35508 KB	Output is correct
31	Correct	158 ms	37476 KB	Output is correct
32	Correct	179 ms	37756 KB	Output is correct
33	Correct	158 ms	37708 KB	Output is correct
34	Correct	160 ms	37896 KB	Output is correct
35	Correct	161 ms	37656 KB	Output is correct
36	Correct	194 ms	37612 KB	Output is correct
37	Correct	168 ms	37844 KB	Output is correct
38	Correct	179 ms	37740 KB	Output is correct
39	Correct	173 ms	38088 KB	Output is correct
40	Correct	186 ms	37900 KB	Output is correct
41	Correct	64 ms	35540 KB	Output is correct
42	Correct	59 ms	36688 KB	Output is correct
43	Correct	67 ms	36684 KB	Output is correct
44	Correct	57 ms	35508 KB	Output is correct
45	Correct	71 ms	36588 KB	Output is correct
46	Correct	65 ms	35552 KB	Output is correct
47	Correct	49 ms	36428 KB	Output is correct
48	Correct	43 ms	35788 KB	Output is correct
49	Correct	52 ms	36492 KB	Output is correct
50	Correct	54 ms	35728 KB	Output is correct
51	Correct	195 ms	36768 KB	Output is correct
52	Correct	193 ms	37460 KB	Output is correct
53	Correct	163 ms	36796 KB	Output is correct
54	Correct	212 ms	37480 KB	Output is correct
55	Correct	175 ms	36868 KB	Output is correct

Subtask #10
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	31700 KB	Output is correct
2	Correct	19 ms	31572 KB	Output is correct
3	Correct	24 ms	31612 KB	Output is correct
4	Correct	19 ms	31532 KB	Output is correct
5	Correct	20 ms	31532 KB	Output is correct
6	Correct	20 ms	31616 KB	Output is correct
7	Correct	22 ms	31588 KB	Output is correct
8	Correct	19 ms	31580 KB	Output is correct
9	Correct	23 ms	31528 KB	Output is correct
10	Correct	18 ms	31628 KB	Output is correct
11	Correct	22 ms	31600 KB	Output is correct
12	Correct	19 ms	31640 KB	Output is correct
13	Correct	18 ms	31532 KB	Output is correct
14	Correct	20 ms	31528 KB	Output is correct
15	Correct	18 ms	31632 KB	Output is correct
16	Correct	22 ms	31520 KB	Output is correct
17	Correct	21 ms	31632 KB	Output is correct
18	Correct	22 ms	31624 KB	Output is correct
19	Correct	20 ms	31632 KB	Output is correct
20	Correct	20 ms	31572 KB	Output is correct
21	Correct	19 ms	31604 KB	Output is correct
22	Correct	20 ms	31640 KB	Output is correct
23	Correct	20 ms	31704 KB	Output is correct
24	Correct	19 ms	31640 KB	Output is correct
25	Correct	23 ms	31632 KB	Output is correct
26	Correct	44 ms	35768 KB	Output is correct
27	Correct	59 ms	36612 KB	Output is correct
28	Correct	42 ms	35660 KB	Output is correct
29	Correct	52 ms	36264 KB	Output is correct
30	Correct	40 ms	35508 KB	Output is correct
31	Correct	158 ms	37476 KB	Output is correct
32	Correct	179 ms	37756 KB	Output is correct
33	Correct	158 ms	37708 KB	Output is correct
34	Correct	160 ms	37896 KB	Output is correct
35	Correct	161 ms	37656 KB	Output is correct
36	Correct	194 ms	37612 KB	Output is correct
37	Correct	168 ms	37844 KB	Output is correct
38	Correct	179 ms	37740 KB	Output is correct
39	Correct	173 ms	38088 KB	Output is correct
40	Correct	186 ms	37900 KB	Output is correct
41	Correct	64 ms	35540 KB	Output is correct
42	Correct	59 ms	36688 KB	Output is correct
43	Correct	67 ms	36684 KB	Output is correct
44	Correct	57 ms	35508 KB	Output is correct
45	Correct	71 ms	36588 KB	Output is correct
46	Correct	65 ms	35552 KB	Output is correct
47	Correct	49 ms	36428 KB	Output is correct
48	Correct	43 ms	35788 KB	Output is correct
49	Correct	52 ms	36492 KB	Output is correct
50	Correct	54 ms	35728 KB	Output is correct
51	Correct	195 ms	36768 KB	Output is correct
52	Correct	193 ms	37460 KB	Output is correct
53	Correct	163 ms	36796 KB	Output is correct
54	Correct	212 ms	37480 KB	Output is correct
55	Correct	175 ms	36868 KB	Output is correct
56	Execution timed out	1085 ms	70940 KB	Time limit exceeded
57	Halted	0 ms	0 KB	-

Submission #572406

Compilation message