oj.uz

답안 #572393

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
572393 2022-06-04T10:32:11 Z MODDI Pilot (NOI19_pilot) C++14
89 / 100
 1000 ms 71092 KB 
#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];
int find(int v){
	if(v == parent[v])
		return v;
	return parent[v] = find(parent[v]);
}
ll rez = 0;
void mrg(int a, int b){
	a = find(a);
	b = find(b);
	if(a != b){
		rez -= (sz[a] * (sz[a] + 1) * 1LL) / 2;
		rez -= (sz[b] * (sz[b] + 1)*1LL) / 2;
		sz[a] += sz[b];
		rez += (sz[a] * (sz[a] + 1)*1LL) / 2;
		parent[b] = a;
	}
}
vl G[maxn];
ll ans[maxn];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i = 0; i < n; i++){
		parent[i] = i;
		sz[i] = 1;
	}
	for(int i = 0; i < n; i++){
		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 16 ms 31592 KB Output is correct
3 Correct 16 ms 31568 KB Output is correct
4 Correct 16 ms 31616 KB Output is correct
5 Correct 21 ms 31608 KB Output is correct
6 Correct 17 ms 31568 KB Output is correct
7 Correct 18 ms 31552 KB Output is correct
8 Correct 17 ms 31572 KB Output is correct
9 Correct 16 ms 31540 KB Output is correct
10 Correct 20 ms 31536 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 31572 KB Output is correct
2 Correct 16 ms 31592 KB Output is correct
3 Correct 16 ms 31568 KB Output is correct
4 Correct 16 ms 31616 KB Output is correct
5 Correct 21 ms 31608 KB Output is correct
6 Correct 17 ms 31568 KB Output is correct
7 Correct 18 ms 31552 KB Output is correct
8 Correct 17 ms 31572 KB Output is correct
9 Correct 16 ms 31540 KB Output is correct
10 Correct 20 ms 31536 KB Output is correct
11 Correct 17 ms 31580 KB Output is correct
12 Correct 17 ms 31544 KB Output is correct
13 Correct 17 ms 31636 KB Output is correct
14 Correct 18 ms 31620 KB Output is correct
15 Correct 17 ms 31528 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 31572 KB Output is correct
2 Correct 16 ms 31592 KB Output is correct
3 Correct 16 ms 31568 KB Output is correct
4 Correct 16 ms 31616 KB Output is correct
5 Correct 21 ms 31608 KB Output is correct
6 Correct 17 ms 31568 KB Output is correct
7 Correct 18 ms 31552 KB Output is correct
8 Correct 17 ms 31572 KB Output is correct
9 Correct 16 ms 31540 KB Output is correct
10 Correct 20 ms 31536 KB Output is correct
11 Correct 17 ms 31580 KB Output is correct
12 Correct 17 ms 31544 KB Output is correct
13 Correct 17 ms 31636 KB Output is correct
14 Correct 18 ms 31620 KB Output is correct
15 Correct 17 ms 31528 KB Output is correct
16 Correct 16 ms 31572 KB Output is correct
17 Correct 20 ms 31620 KB Output is correct
18 Correct 16 ms 31564 KB Output is correct
19 Correct 16 ms 31572 KB Output is correct
20 Correct 20 ms 31568 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 31572 KB Output is correct
2 Correct 16 ms 31592 KB Output is correct
3 Correct 16 ms 31568 KB Output is correct
4 Correct 16 ms 31616 KB Output is correct
5 Correct 21 ms 31608 KB Output is correct
6 Correct 17 ms 31568 KB Output is correct
7 Correct 18 ms 31552 KB Output is correct
8 Correct 17 ms 31572 KB Output is correct
9 Correct 16 ms 31540 KB Output is correct
10 Correct 20 ms 31536 KB Output is correct
11 Correct 17 ms 31580 KB Output is correct
12 Correct 17 ms 31544 KB Output is correct
13 Correct 17 ms 31636 KB Output is correct
14 Correct 18 ms 31620 KB Output is correct
15 Correct 17 ms 31528 KB Output is correct
16 Correct 16 ms 31572 KB Output is correct
17 Correct 20 ms 31620 KB Output is correct
18 Correct 16 ms 31564 KB Output is correct
19 Correct 16 ms 31572 KB Output is correct
20 Correct 20 ms 31568 KB Output is correct
21 Correct 18 ms 31620 KB Output is correct
22 Correct 22 ms 31700 KB Output is correct
23 Correct 20 ms 31572 KB Output is correct
24 Correct 18 ms 31644 KB Output is correct
25 Correct 22 ms 31676 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 35184 KB Output is correct
2 Correct 59 ms 36112 KB Output is correct
3 Correct 39 ms 35068 KB Output is correct
4 Correct 46 ms 35828 KB Output is correct
5 Correct 43 ms 35016 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 153 ms 37004 KB Output is correct
2 Correct 166 ms 37084 KB Output is correct
3 Correct 156 ms 36932 KB Output is correct
4 Correct 160 ms 37196 KB Output is correct
5 Correct 161 ms 36924 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 37092 KB Output is correct
2 Correct 188 ms 36936 KB Output is correct
3 Correct 170 ms 36832 KB Output is correct
4 Correct 165 ms 37320 KB Output is correct
5 Correct 168 ms 37048 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 31572 KB Output is correct
2 Correct 16 ms 31592 KB Output is correct
3 Correct 16 ms 31568 KB Output is correct
4 Correct 16 ms 31616 KB Output is correct
5 Correct 21 ms 31608 KB Output is correct
6 Correct 17 ms 31568 KB Output is correct
7 Correct 18 ms 31552 KB Output is correct
8 Correct 17 ms 31572 KB Output is correct
9 Correct 16 ms 31540 KB Output is correct
10 Correct 20 ms 31536 KB Output is correct
11 Correct 40 ms 35184 KB Output is correct
12 Correct 59 ms 36112 KB Output is correct
13 Correct 39 ms 35068 KB Output is correct
14 Correct 46 ms 35828 KB Output is correct
15 Correct 43 ms 35016 KB Output is correct
16 Correct 39 ms 35016 KB Output is correct
17 Correct 58 ms 36124 KB Output is correct
18 Correct 59 ms 36176 KB Output is correct
19 Correct 41 ms 35028 KB Output is correct
20 Correct 53 ms 36104 KB Output is correct
21 Correct 41 ms 35080 KB Output is correct
22 Correct 51 ms 35916 KB Output is correct
23 Correct 38 ms 35368 KB Output is correct
24 Correct 54 ms 35820 KB Output is correct
25 Correct 49 ms 35216 KB Output is correct

Subtask #9
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 31572 KB Output is correct
2 Correct 16 ms 31592 KB Output is correct
3 Correct 16 ms 31568 KB Output is correct
4 Correct 16 ms 31616 KB Output is correct
5 Correct 21 ms 31608 KB Output is correct
6 Correct 17 ms 31568 KB Output is correct
7 Correct 18 ms 31552 KB Output is correct
8 Correct 17 ms 31572 KB Output is correct
9 Correct 16 ms 31540 KB Output is correct
10 Correct 20 ms 31536 KB Output is correct
11 Correct 17 ms 31580 KB Output is correct
12 Correct 17 ms 31544 KB Output is correct
13 Correct 17 ms 31636 KB Output is correct
14 Correct 18 ms 31620 KB Output is correct
15 Correct 17 ms 31528 KB Output is correct
16 Correct 16 ms 31572 KB Output is correct
17 Correct 20 ms 31620 KB Output is correct
18 Correct 16 ms 31564 KB Output is correct
19 Correct 16 ms 31572 KB Output is correct
20 Correct 20 ms 31568 KB Output is correct
21 Correct 18 ms 31620 KB Output is correct
22 Correct 22 ms 31700 KB Output is correct
23 Correct 20 ms 31572 KB Output is correct
24 Correct 18 ms 31644 KB Output is correct
25 Correct 22 ms 31676 KB Output is correct
26 Correct 40 ms 35184 KB Output is correct
27 Correct 59 ms 36112 KB Output is correct
28 Correct 39 ms 35068 KB Output is correct
29 Correct 46 ms 35828 KB Output is correct
30 Correct 43 ms 35016 KB Output is correct
31 Correct 153 ms 37004 KB Output is correct
32 Correct 166 ms 37084 KB Output is correct
33 Correct 156 ms 36932 KB Output is correct
34 Correct 160 ms 37196 KB Output is correct
35 Correct 161 ms 36924 KB Output is correct
36 Correct 165 ms 37092 KB Output is correct
37 Correct 188 ms 36936 KB Output is correct
38 Correct 170 ms 36832 KB Output is correct
39 Correct 165 ms 37320 KB Output is correct
40 Correct 168 ms 37048 KB Output is correct
41 Correct 39 ms 35016 KB Output is correct
42 Correct 58 ms 36124 KB Output is correct
43 Correct 59 ms 36176 KB Output is correct
44 Correct 41 ms 35028 KB Output is correct
45 Correct 53 ms 36104 KB Output is correct
46 Correct 41 ms 35080 KB Output is correct
47 Correct 51 ms 35916 KB Output is correct
48 Correct 38 ms 35368 KB Output is correct
49 Correct 54 ms 35820 KB Output is correct
50 Correct 49 ms 35216 KB Output is correct
51 Correct 171 ms 36004 KB Output is correct
52 Correct 199 ms 36524 KB Output is correct
53 Correct 173 ms 36028 KB Output is correct
54 Correct 179 ms 36628 KB Output is correct
55 Correct 200 ms 36044 KB Output is correct

Subtask #10
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 31572 KB Output is correct
2 Correct 16 ms 31592 KB Output is correct
3 Correct 16 ms 31568 KB Output is correct
4 Correct 16 ms 31616 KB Output is correct
5 Correct 21 ms 31608 KB Output is correct
6 Correct 17 ms 31568 KB Output is correct
7 Correct 18 ms 31552 KB Output is correct
8 Correct 17 ms 31572 KB Output is correct
9 Correct 16 ms 31540 KB Output is correct
10 Correct 20 ms 31536 KB Output is correct
11 Correct 17 ms 31580 KB Output is correct
12 Correct 17 ms 31544 KB Output is correct
13 Correct 17 ms 31636 KB Output is correct
14 Correct 18 ms 31620 KB Output is correct
15 Correct 17 ms 31528 KB Output is correct
16 Correct 16 ms 31572 KB Output is correct
17 Correct 20 ms 31620 KB Output is correct
18 Correct 16 ms 31564 KB Output is correct
19 Correct 16 ms 31572 KB Output is correct
20 Correct 20 ms 31568 KB Output is correct
21 Correct 18 ms 31620 KB Output is correct
22 Correct 22 ms 31700 KB Output is correct
23 Correct 20 ms 31572 KB Output is correct
24 Correct 18 ms 31644 KB Output is correct
25 Correct 22 ms 31676 KB Output is correct
26 Correct 40 ms 35184 KB Output is correct
27 Correct 59 ms 36112 KB Output is correct
28 Correct 39 ms 35068 KB Output is correct
29 Correct 46 ms 35828 KB Output is correct
30 Correct 43 ms 35016 KB Output is correct
31 Correct 153 ms 37004 KB Output is correct
32 Correct 166 ms 37084 KB Output is correct
33 Correct 156 ms 36932 KB Output is correct
34 Correct 160 ms 37196 KB Output is correct
35 Correct 161 ms 36924 KB Output is correct
36 Correct 165 ms 37092 KB Output is correct
37 Correct 188 ms 36936 KB Output is correct
38 Correct 170 ms 36832 KB Output is correct
39 Correct 165 ms 37320 KB Output is correct
40 Correct 168 ms 37048 KB Output is correct
41 Correct 39 ms 35016 KB Output is correct
42 Correct 58 ms 36124 KB Output is correct
43 Correct 59 ms 36176 KB Output is correct
44 Correct 41 ms 35028 KB Output is correct
45 Correct 53 ms 36104 KB Output is correct
46 Correct 41 ms 35080 KB Output is correct
47 Correct 51 ms 35916 KB Output is correct
48 Correct 38 ms 35368 KB Output is correct
49 Correct 54 ms 35820 KB Output is correct
50 Correct 49 ms 35216 KB Output is correct
51 Correct 171 ms 36004 KB Output is correct
52 Correct 199 ms 36524 KB Output is correct
53 Correct 173 ms 36028 KB Output is correct
54 Correct 179 ms 36628 KB Output is correct
55 Correct 200 ms 36044 KB Output is correct
56 Execution timed out 1091 ms 71092 KB Time limit exceeded
57 Halted 0 ms 0 KB -