답안 #572403

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
572403	2022-06-04T10:38:00 Z	MODDI	Pilot (NOI19_pilot)	C++14	89 / 100	1000 ms	71008 KB

pilot

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
const int maxn = 1e6 + 5;
int n, q;
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;
}
vl G[maxn];
ll ans[maxn];
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	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

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	31572 KB	Output is correct
2	Correct	17 ms	31572 KB	Output is correct
3	Correct	17 ms	31536 KB	Output is correct
4	Correct	17 ms	31572 KB	Output is correct
5	Correct	18 ms	31572 KB	Output is correct
6	Correct	21 ms	31632 KB	Output is correct
7	Correct	16 ms	31572 KB	Output is correct
8	Correct	16 ms	31572 KB	Output is correct
9	Correct	21 ms	31564 KB	Output is correct
10	Correct	17 ms	31572 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	31572 KB	Output is correct
2	Correct	17 ms	31572 KB	Output is correct
3	Correct	17 ms	31536 KB	Output is correct
4	Correct	17 ms	31572 KB	Output is correct
5	Correct	18 ms	31572 KB	Output is correct
6	Correct	21 ms	31632 KB	Output is correct
7	Correct	16 ms	31572 KB	Output is correct
8	Correct	16 ms	31572 KB	Output is correct
9	Correct	21 ms	31564 KB	Output is correct
10	Correct	17 ms	31572 KB	Output is correct
11	Correct	18 ms	31572 KB	Output is correct
12	Correct	17 ms	31572 KB	Output is correct
13	Correct	16 ms	31644 KB	Output is correct
14	Correct	20 ms	31616 KB	Output is correct
15	Correct	17 ms	31536 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	31572 KB	Output is correct
2	Correct	17 ms	31572 KB	Output is correct
3	Correct	17 ms	31536 KB	Output is correct
4	Correct	17 ms	31572 KB	Output is correct
5	Correct	18 ms	31572 KB	Output is correct
6	Correct	21 ms	31632 KB	Output is correct
7	Correct	16 ms	31572 KB	Output is correct
8	Correct	16 ms	31572 KB	Output is correct
9	Correct	21 ms	31564 KB	Output is correct
10	Correct	17 ms	31572 KB	Output is correct
11	Correct	18 ms	31572 KB	Output is correct
12	Correct	17 ms	31572 KB	Output is correct
13	Correct	16 ms	31644 KB	Output is correct
14	Correct	20 ms	31616 KB	Output is correct
15	Correct	17 ms	31536 KB	Output is correct
16	Correct	16 ms	31556 KB	Output is correct
17	Correct	15 ms	31544 KB	Output is correct
18	Correct	16 ms	31648 KB	Output is correct
19	Correct	16 ms	31564 KB	Output is correct
20	Correct	16 ms	31620 KB	Output is correct

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	31572 KB	Output is correct
2	Correct	17 ms	31572 KB	Output is correct
3	Correct	17 ms	31536 KB	Output is correct
4	Correct	17 ms	31572 KB	Output is correct
5	Correct	18 ms	31572 KB	Output is correct
6	Correct	21 ms	31632 KB	Output is correct
7	Correct	16 ms	31572 KB	Output is correct
8	Correct	16 ms	31572 KB	Output is correct
9	Correct	21 ms	31564 KB	Output is correct
10	Correct	17 ms	31572 KB	Output is correct
11	Correct	18 ms	31572 KB	Output is correct
12	Correct	17 ms	31572 KB	Output is correct
13	Correct	16 ms	31644 KB	Output is correct
14	Correct	20 ms	31616 KB	Output is correct
15	Correct	17 ms	31536 KB	Output is correct
16	Correct	16 ms	31556 KB	Output is correct
17	Correct	15 ms	31544 KB	Output is correct
18	Correct	16 ms	31648 KB	Output is correct
19	Correct	16 ms	31564 KB	Output is correct
20	Correct	16 ms	31620 KB	Output is correct
21	Correct	18 ms	31572 KB	Output is correct
22	Correct	19 ms	31652 KB	Output is correct
23	Correct	24 ms	31572 KB	Output is correct
24	Correct	21 ms	31584 KB	Output is correct
25	Correct	18 ms	31648 KB	Output is correct

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	35272 KB	Output is correct
2	Correct	50 ms	36136 KB	Output is correct
3	Correct	39 ms	35108 KB	Output is correct
4	Correct	58 ms	35704 KB	Output is correct
5	Correct	45 ms	35040 KB	Output is correct

Subtask #6
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	156 ms	37092 KB	Output is correct
2	Correct	159 ms	37128 KB	Output is correct
3	Correct	172 ms	37052 KB	Output is correct
4	Correct	150 ms	37244 KB	Output is correct
5	Correct	153 ms	36980 KB	Output is correct

Subtask #7
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	169 ms	37148 KB	Output is correct
2	Correct	160 ms	36980 KB	Output is correct
3	Correct	162 ms	36916 KB	Output is correct
4	Correct	173 ms	37280 KB	Output is correct
5	Correct	178 ms	37020 KB	Output is correct

Subtask #8
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	31572 KB	Output is correct
2	Correct	17 ms	31572 KB	Output is correct
3	Correct	17 ms	31536 KB	Output is correct
4	Correct	17 ms	31572 KB	Output is correct
5	Correct	18 ms	31572 KB	Output is correct
6	Correct	21 ms	31632 KB	Output is correct
7	Correct	16 ms	31572 KB	Output is correct
8	Correct	16 ms	31572 KB	Output is correct
9	Correct	21 ms	31564 KB	Output is correct
10	Correct	17 ms	31572 KB	Output is correct
11	Correct	37 ms	35272 KB	Output is correct
12	Correct	50 ms	36136 KB	Output is correct
13	Correct	39 ms	35108 KB	Output is correct
14	Correct	58 ms	35704 KB	Output is correct
15	Correct	45 ms	35040 KB	Output is correct
16	Correct	35 ms	35060 KB	Output is correct
17	Correct	50 ms	36172 KB	Output is correct
18	Correct	55 ms	36184 KB	Output is correct
19	Correct	53 ms	35020 KB	Output is correct
20	Correct	58 ms	36088 KB	Output is correct
21	Correct	41 ms	34980 KB	Output is correct
22	Correct	49 ms	35840 KB	Output is correct
23	Correct	41 ms	35356 KB	Output is correct
24	Correct	52 ms	35804 KB	Output is correct
25	Correct	39 ms	35200 KB	Output is correct

Subtask #9
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	31572 KB	Output is correct
2	Correct	17 ms	31572 KB	Output is correct
3	Correct	17 ms	31536 KB	Output is correct
4	Correct	17 ms	31572 KB	Output is correct
5	Correct	18 ms	31572 KB	Output is correct
6	Correct	21 ms	31632 KB	Output is correct
7	Correct	16 ms	31572 KB	Output is correct
8	Correct	16 ms	31572 KB	Output is correct
9	Correct	21 ms	31564 KB	Output is correct
10	Correct	17 ms	31572 KB	Output is correct
11	Correct	18 ms	31572 KB	Output is correct
12	Correct	17 ms	31572 KB	Output is correct
13	Correct	16 ms	31644 KB	Output is correct
14	Correct	20 ms	31616 KB	Output is correct
15	Correct	17 ms	31536 KB	Output is correct
16	Correct	16 ms	31556 KB	Output is correct
17	Correct	15 ms	31544 KB	Output is correct
18	Correct	16 ms	31648 KB	Output is correct
19	Correct	16 ms	31564 KB	Output is correct
20	Correct	16 ms	31620 KB	Output is correct
21	Correct	18 ms	31572 KB	Output is correct
22	Correct	19 ms	31652 KB	Output is correct
23	Correct	24 ms	31572 KB	Output is correct
24	Correct	21 ms	31584 KB	Output is correct
25	Correct	18 ms	31648 KB	Output is correct
26	Correct	37 ms	35272 KB	Output is correct
27	Correct	50 ms	36136 KB	Output is correct
28	Correct	39 ms	35108 KB	Output is correct
29	Correct	58 ms	35704 KB	Output is correct
30	Correct	45 ms	35040 KB	Output is correct
31	Correct	156 ms	37092 KB	Output is correct
32	Correct	159 ms	37128 KB	Output is correct
33	Correct	172 ms	37052 KB	Output is correct
34	Correct	150 ms	37244 KB	Output is correct
35	Correct	153 ms	36980 KB	Output is correct
36	Correct	169 ms	37148 KB	Output is correct
37	Correct	160 ms	36980 KB	Output is correct
38	Correct	162 ms	36916 KB	Output is correct
39	Correct	173 ms	37280 KB	Output is correct
40	Correct	178 ms	37020 KB	Output is correct
41	Correct	35 ms	35060 KB	Output is correct
42	Correct	50 ms	36172 KB	Output is correct
43	Correct	55 ms	36184 KB	Output is correct
44	Correct	53 ms	35020 KB	Output is correct
45	Correct	58 ms	36088 KB	Output is correct
46	Correct	41 ms	34980 KB	Output is correct
47	Correct	49 ms	35840 KB	Output is correct
48	Correct	41 ms	35356 KB	Output is correct
49	Correct	52 ms	35804 KB	Output is correct
50	Correct	39 ms	35200 KB	Output is correct
51	Correct	217 ms	36024 KB	Output is correct
52	Correct	180 ms	36580 KB	Output is correct
53	Correct	168 ms	36120 KB	Output is correct
54	Correct	189 ms	36620 KB	Output is correct
55	Correct	157 ms	36088 KB	Output is correct

Subtask #10
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	31572 KB	Output is correct
2	Correct	17 ms	31572 KB	Output is correct
3	Correct	17 ms	31536 KB	Output is correct
4	Correct	17 ms	31572 KB	Output is correct
5	Correct	18 ms	31572 KB	Output is correct
6	Correct	21 ms	31632 KB	Output is correct
7	Correct	16 ms	31572 KB	Output is correct
8	Correct	16 ms	31572 KB	Output is correct
9	Correct	21 ms	31564 KB	Output is correct
10	Correct	17 ms	31572 KB	Output is correct
11	Correct	18 ms	31572 KB	Output is correct
12	Correct	17 ms	31572 KB	Output is correct
13	Correct	16 ms	31644 KB	Output is correct
14	Correct	20 ms	31616 KB	Output is correct
15	Correct	17 ms	31536 KB	Output is correct
16	Correct	16 ms	31556 KB	Output is correct
17	Correct	15 ms	31544 KB	Output is correct
18	Correct	16 ms	31648 KB	Output is correct
19	Correct	16 ms	31564 KB	Output is correct
20	Correct	16 ms	31620 KB	Output is correct
21	Correct	18 ms	31572 KB	Output is correct
22	Correct	19 ms	31652 KB	Output is correct
23	Correct	24 ms	31572 KB	Output is correct
24	Correct	21 ms	31584 KB	Output is correct
25	Correct	18 ms	31648 KB	Output is correct
26	Correct	37 ms	35272 KB	Output is correct
27	Correct	50 ms	36136 KB	Output is correct
28	Correct	39 ms	35108 KB	Output is correct
29	Correct	58 ms	35704 KB	Output is correct
30	Correct	45 ms	35040 KB	Output is correct
31	Correct	156 ms	37092 KB	Output is correct
32	Correct	159 ms	37128 KB	Output is correct
33	Correct	172 ms	37052 KB	Output is correct
34	Correct	150 ms	37244 KB	Output is correct
35	Correct	153 ms	36980 KB	Output is correct
36	Correct	169 ms	37148 KB	Output is correct
37	Correct	160 ms	36980 KB	Output is correct
38	Correct	162 ms	36916 KB	Output is correct
39	Correct	173 ms	37280 KB	Output is correct
40	Correct	178 ms	37020 KB	Output is correct
41	Correct	35 ms	35060 KB	Output is correct
42	Correct	50 ms	36172 KB	Output is correct
43	Correct	55 ms	36184 KB	Output is correct
44	Correct	53 ms	35020 KB	Output is correct
45	Correct	58 ms	36088 KB	Output is correct
46	Correct	41 ms	34980 KB	Output is correct
47	Correct	49 ms	35840 KB	Output is correct
48	Correct	41 ms	35356 KB	Output is correct
49	Correct	52 ms	35804 KB	Output is correct
50	Correct	39 ms	35200 KB	Output is correct
51	Correct	217 ms	36024 KB	Output is correct
52	Correct	180 ms	36580 KB	Output is correct
53	Correct	168 ms	36120 KB	Output is correct
54	Correct	189 ms	36620 KB	Output is correct
55	Correct	157 ms	36088 KB	Output is correct
56	Execution timed out	1090 ms	71008 KB	Time limit exceeded
57	Halted	0 ms	0 KB	-

답안 #572403

Compilation message