oj.uz

Submission #455116

# Submission time Handle Problem Language Result Execution time Memory
455116 2021-08-05T12:53:57 Z _adis Pilot (NOI19_pilot) C++14
100 / 100
 641 ms 59900 KB 
/*input
511 10
515 485 101 214 126 998 591 161 830 607 620 687 433 336 403 640 403 490 60 86 360 65 23 325 457 600 313 631 322 336 75 849 215 327 235 565 157 792 372 973 405 257 432 828 760 876 923 262 688 13 768 443 255 409 705 75 588 717 65 999 193 221 858 495 204 416 358 685 519 926 533 186 749 667 244 265 729 594 52 740 137 586 556 71 19 84 114 812 627 626 659 468 675 15 497 341 773 757 163 556 582 134 759 864 890 152 183 458 687 795 61 69 521 265 10 76 922 526 899 577 965 94 641 442 720 539 731 582 366 536 779 339 622 825 90 438 930 35 4 956 258 5 198 378 137 452 228 255 714 411 238 886 423 986 532 129 463 365 335 940 708 538 740 864 990 484 869 166 165 23 798 84 371 298 535 188 880 418 876 588 540 131 747 434 709 284 766 966 644 75 55 953 907 10 677 260 833 363 561 214 358 532 3 295 762 897 229 443 961 301 382 186 896 496 906 356 581 968 619 51 602 762 377 210 111 529 750 766 500 811 678 416 241 133 78 727 582 744 472 889 497 465 171 249 944 112 575 206 890 756 748 545 606 164 795 398 983 493 57 980 114 964 19 917 361 743 844 446 704 267 876 24 184 127 572 436 400 19 691 404 582 912 500 79 42 98 848 582 42 778 19 556 866 455 202 144 564 903 859 153 668 185 241 289 431 163 741 236 326 985 993 319 659 279 812 154 712 411 436 380 509 500 301 772 971 893 86 866 808 68 533 984 813 613 501 553 760 559 550 29 23 756 321 180 155 367 68 582 335 217 927 971 93 699 496 649 877 341 611 404 823 811 635 799 951 292 799 762 461 13 767 770 585 132 644 877 424 131 812 113 719 997 271 682 349 422 686 110 683 552 308 163 149 563 837 773 495 697 883 80 140 497 746 70 53 384 309 388 285 943 325 27 217 299 453 374 410 409 24 46 933 1000 47 64 59 585 465 25 118 441 437 944 63 127 295 649 252 872 716 793 939 992 563 254 665 963 625 499 480 3 526 724 227 886 249 874 124 788 667 842 36 220 744 695 937 862 283 375 115 966 150 374 984 685 517 301 465 222 142 243 386 332 531 793 418 239 122 470 395 348 858 433 435 132 626 388 585 815 80 396 796 573 323 501 639 187 48 665 961 119 227 
140 211 123 309 256 359 344 113 139 137
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1e2;
int a[N], mark[N], n, q, xuoi[N], nguoc[N], lenxuoi, lennguoc;
long long sum[N], pref[N];
pair<int, int> b[N];
main() {
	cin.tie(0)->sync_with_stdio(0);
	//freopen("pilot.inp", "r", stdin);
	//freopen("pilot.out", "w", stdout);
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		b[i].first = a[i];
		b[i].second = i;
	}
	for (int i = 1; i <= 1000000; i++) pref[i] = pref[i - 1] + i;
	sort(b + 1, b + 1 + n);
	int st = 1;
	for (int i = 1; i <= 1000000; i++)
	{
		long long diff = 0;
		while (b[st].first == i)
		{
			mark[b[st].second] = 1;
			if (mark[b[st].second + 1])
			{
				lenxuoi = xuoi[b[st].second + 1] - (b[st].second + 1) + 1;
			}
			if (mark[b[st].second - 1])
			{
				lennguoc = b[st].second - 1 - nguoc[b[st].second - 1] + 1;
			}
			if (!mark[b[st].second - 1] && !mark[b[st].second + 1])
			{
				diff += pref[1];
				xuoi[b[st].second] = b[st].second;
				nguoc[b[st].second] = b[st].second;
			}
			else if (!mark[b[st].second - 1] && mark[b[st].second + 1])
			{
				diff += lenxuoi + 1;
				xuoi[b[st].second] = xuoi[b[st].second + 1];
				nguoc[xuoi[b[st].second + 1]] = b[st].second;
			}
			else if (mark[b[st].second - 1] && !mark[b[st].second + 1])
			{
				diff += lennguoc + 1;
				nguoc[b[st].second] = nguoc[b[st].second - 1];
				xuoi[nguoc[b[st].second]] = b[st].second;
			}
			else
			{
				diff += pref[lennguoc + lenxuoi + 1] - pref[lennguoc] - pref[lenxuoi];
				xuoi[nguoc[b[st].second - 1]] = xuoi[b[st].second + 1];
				nguoc[xuoi[b[st].second + 1]] = nguoc[b[st].second - 1];
			}
			st++;
		}
		sum[i] = sum[i - 1] + diff;
	}
	for (int i = 1; i <= q; i++)
	{
		int query;
		cin >> query;
		cout << sum[query] << "\n";
	}
	return 0;
}

Compilation message

pilot.cpp:12:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   12 | main() {
      | ^~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15912 KB Output is correct
2 Correct 15 ms 15920 KB Output is correct
3 Correct 15 ms 15960 KB Output is correct
4 Correct 13 ms 15936 KB Output is correct
5 Correct 14 ms 15948 KB Output is correct
6 Correct 15 ms 15924 KB Output is correct
7 Correct 14 ms 15904 KB Output is correct
8 Correct 13 ms 15992 KB Output is correct
9 Correct 15 ms 15964 KB Output is correct
10 Correct 13 ms 15948 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15912 KB Output is correct
2 Correct 15 ms 15920 KB Output is correct
3 Correct 15 ms 15960 KB Output is correct
4 Correct 13 ms 15936 KB Output is correct
5 Correct 14 ms 15948 KB Output is correct
6 Correct 15 ms 15924 KB Output is correct
7 Correct 14 ms 15904 KB Output is correct
8 Correct 13 ms 15992 KB Output is correct
9 Correct 15 ms 15964 KB Output is correct
10 Correct 13 ms 15948 KB Output is correct
11 Correct 13 ms 15948 KB Output is correct
12 Correct 13 ms 15912 KB Output is correct
13 Correct 13 ms 15948 KB Output is correct
14 Correct 13 ms 15952 KB Output is correct
15 Correct 13 ms 15912 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15912 KB Output is correct
2 Correct 15 ms 15920 KB Output is correct
3 Correct 15 ms 15960 KB Output is correct
4 Correct 13 ms 15936 KB Output is correct
5 Correct 14 ms 15948 KB Output is correct
6 Correct 15 ms 15924 KB Output is correct
7 Correct 14 ms 15904 KB Output is correct
8 Correct 13 ms 15992 KB Output is correct
9 Correct 15 ms 15964 KB Output is correct
10 Correct 13 ms 15948 KB Output is correct
11 Correct 13 ms 15948 KB Output is correct
12 Correct 13 ms 15912 KB Output is correct
13 Correct 13 ms 15948 KB Output is correct
14 Correct 13 ms 15952 KB Output is correct
15 Correct 13 ms 15912 KB Output is correct
16 Correct 13 ms 15976 KB Output is correct
17 Correct 13 ms 15948 KB Output is correct
18 Correct 13 ms 16020 KB Output is correct
19 Correct 13 ms 15948 KB Output is correct
20 Correct 13 ms 15988 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15912 KB Output is correct
2 Correct 15 ms 15920 KB Output is correct
3 Correct 15 ms 15960 KB Output is correct
4 Correct 13 ms 15936 KB Output is correct
5 Correct 14 ms 15948 KB Output is correct
6 Correct 15 ms 15924 KB Output is correct
7 Correct 14 ms 15904 KB Output is correct
8 Correct 13 ms 15992 KB Output is correct
9 Correct 15 ms 15964 KB Output is correct
10 Correct 13 ms 15948 KB Output is correct
11 Correct 13 ms 15948 KB Output is correct
12 Correct 13 ms 15912 KB Output is correct
13 Correct 13 ms 15948 KB Output is correct
14 Correct 13 ms 15952 KB Output is correct
15 Correct 13 ms 15912 KB Output is correct
16 Correct 13 ms 15976 KB Output is correct
17 Correct 13 ms 15948 KB Output is correct
18 Correct 13 ms 16020 KB Output is correct
19 Correct 13 ms 15948 KB Output is correct
20 Correct 13 ms 15988 KB Output is correct
21 Correct 13 ms 15944 KB Output is correct
22 Correct 14 ms 15948 KB Output is correct
23 Correct 14 ms 16024 KB Output is correct
24 Correct 14 ms 16040 KB Output is correct
25 Correct 14 ms 15948 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 18756 KB Output is correct
2 Correct 37 ms 18888 KB Output is correct
3 Correct 34 ms 18644 KB Output is correct
4 Correct 35 ms 18628 KB Output is correct
5 Correct 35 ms 18656 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 19904 KB Output is correct
2 Correct 51 ms 19932 KB Output is correct
3 Correct 51 ms 19924 KB Output is correct
4 Correct 52 ms 19932 KB Output is correct
5 Correct 53 ms 19780 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 20056 KB Output is correct
2 Correct 53 ms 20036 KB Output is correct
3 Correct 55 ms 19916 KB Output is correct
4 Correct 58 ms 20076 KB Output is correct
5 Correct 58 ms 20168 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15912 KB Output is correct
2 Correct 15 ms 15920 KB Output is correct
3 Correct 15 ms 15960 KB Output is correct
4 Correct 13 ms 15936 KB Output is correct
5 Correct 14 ms 15948 KB Output is correct
6 Correct 15 ms 15924 KB Output is correct
7 Correct 14 ms 15904 KB Output is correct
8 Correct 13 ms 15992 KB Output is correct
9 Correct 15 ms 15964 KB Output is correct
10 Correct 13 ms 15948 KB Output is correct
11 Correct 35 ms 18756 KB Output is correct
12 Correct 37 ms 18888 KB Output is correct
13 Correct 34 ms 18644 KB Output is correct
14 Correct 35 ms 18628 KB Output is correct
15 Correct 35 ms 18656 KB Output is correct
16 Correct 35 ms 18612 KB Output is correct
17 Correct 36 ms 18936 KB Output is correct
18 Correct 38 ms 18952 KB Output is correct
19 Correct 35 ms 18612 KB Output is correct
20 Correct 38 ms 18804 KB Output is correct
21 Correct 35 ms 18604 KB Output is correct
22 Correct 35 ms 18756 KB Output is correct
23 Correct 37 ms 18884 KB Output is correct
24 Correct 35 ms 18696 KB Output is correct
25 Correct 35 ms 18760 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15912 KB Output is correct
2 Correct 15 ms 15920 KB Output is correct
3 Correct 15 ms 15960 KB Output is correct
4 Correct 13 ms 15936 KB Output is correct
5 Correct 14 ms 15948 KB Output is correct
6 Correct 15 ms 15924 KB Output is correct
7 Correct 14 ms 15904 KB Output is correct
8 Correct 13 ms 15992 KB Output is correct
9 Correct 15 ms 15964 KB Output is correct
10 Correct 13 ms 15948 KB Output is correct
11 Correct 13 ms 15948 KB Output is correct
12 Correct 13 ms 15912 KB Output is correct
13 Correct 13 ms 15948 KB Output is correct
14 Correct 13 ms 15952 KB Output is correct
15 Correct 13 ms 15912 KB Output is correct
16 Correct 13 ms 15976 KB Output is correct
17 Correct 13 ms 15948 KB Output is correct
18 Correct 13 ms 16020 KB Output is correct
19 Correct 13 ms 15948 KB Output is correct
20 Correct 13 ms 15988 KB Output is correct
21 Correct 13 ms 15944 KB Output is correct
22 Correct 14 ms 15948 KB Output is correct
23 Correct 14 ms 16024 KB Output is correct
24 Correct 14 ms 16040 KB Output is correct
25 Correct 14 ms 15948 KB Output is correct
26 Correct 35 ms 18756 KB Output is correct
27 Correct 37 ms 18888 KB Output is correct
28 Correct 34 ms 18644 KB Output is correct
29 Correct 35 ms 18628 KB Output is correct
30 Correct 35 ms 18656 KB Output is correct
31 Correct 50 ms 19904 KB Output is correct
32 Correct 51 ms 19932 KB Output is correct
33 Correct 51 ms 19924 KB Output is correct
34 Correct 52 ms 19932 KB Output is correct
35 Correct 53 ms 19780 KB Output is correct
36 Correct 57 ms 20056 KB Output is correct
37 Correct 53 ms 20036 KB Output is correct
38 Correct 55 ms 19916 KB Output is correct
39 Correct 58 ms 20076 KB Output is correct
40 Correct 58 ms 20168 KB Output is correct
41 Correct 35 ms 18612 KB Output is correct
42 Correct 36 ms 18936 KB Output is correct
43 Correct 38 ms 18952 KB Output is correct
44 Correct 35 ms 18612 KB Output is correct
45 Correct 38 ms 18804 KB Output is correct
46 Correct 35 ms 18604 KB Output is correct
47 Correct 35 ms 18756 KB Output is correct
48 Correct 37 ms 18884 KB Output is correct
49 Correct 35 ms 18696 KB Output is correct
50 Correct 35 ms 18760 KB Output is correct
51 Correct 63 ms 20164 KB Output is correct
52 Correct 67 ms 20104 KB Output is correct
53 Correct 62 ms 20232 KB Output is correct
54 Correct 62 ms 19996 KB Output is correct
55 Correct 59 ms 20180 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15912 KB Output is correct
2 Correct 15 ms 15920 KB Output is correct
3 Correct 15 ms 15960 KB Output is correct
4 Correct 13 ms 15936 KB Output is correct
5 Correct 14 ms 15948 KB Output is correct
6 Correct 15 ms 15924 KB Output is correct
7 Correct 14 ms 15904 KB Output is correct
8 Correct 13 ms 15992 KB Output is correct
9 Correct 15 ms 15964 KB Output is correct
10 Correct 13 ms 15948 KB Output is correct
11 Correct 13 ms 15948 KB Output is correct
12 Correct 13 ms 15912 KB Output is correct
13 Correct 13 ms 15948 KB Output is correct
14 Correct 13 ms 15952 KB Output is correct
15 Correct 13 ms 15912 KB Output is correct
16 Correct 13 ms 15976 KB Output is correct
17 Correct 13 ms 15948 KB Output is correct
18 Correct 13 ms 16020 KB Output is correct
19 Correct 13 ms 15948 KB Output is correct
20 Correct 13 ms 15988 KB Output is correct
21 Correct 13 ms 15944 KB Output is correct
22 Correct 14 ms 15948 KB Output is correct
23 Correct 14 ms 16024 KB Output is correct
24 Correct 14 ms 16040 KB Output is correct
25 Correct 14 ms 15948 KB Output is correct
26 Correct 35 ms 18756 KB Output is correct
27 Correct 37 ms 18888 KB Output is correct
28 Correct 34 ms 18644 KB Output is correct
29 Correct 35 ms 18628 KB Output is correct
30 Correct 35 ms 18656 KB Output is correct
31 Correct 50 ms 19904 KB Output is correct
32 Correct 51 ms 19932 KB Output is correct
33 Correct 51 ms 19924 KB Output is correct
34 Correct 52 ms 19932 KB Output is correct
35 Correct 53 ms 19780 KB Output is correct
36 Correct 57 ms 20056 KB Output is correct
37 Correct 53 ms 20036 KB Output is correct
38 Correct 55 ms 19916 KB Output is correct
39 Correct 58 ms 20076 KB Output is correct
40 Correct 58 ms 20168 KB Output is correct
41 Correct 35 ms 18612 KB Output is correct
42 Correct 36 ms 18936 KB Output is correct
43 Correct 38 ms 18952 KB Output is correct
44 Correct 35 ms 18612 KB Output is correct
45 Correct 38 ms 18804 KB Output is correct
46 Correct 35 ms 18604 KB Output is correct
47 Correct 35 ms 18756 KB Output is correct
48 Correct 37 ms 18884 KB Output is correct
49 Correct 35 ms 18696 KB Output is correct
50 Correct 35 ms 18760 KB Output is correct
51 Correct 63 ms 20164 KB Output is correct
52 Correct 67 ms 20104 KB Output is correct
53 Correct 62 ms 20232 KB Output is correct
54 Correct 62 ms 19996 KB Output is correct
55 Correct 59 ms 20180 KB Output is correct
56 Correct 577 ms 58476 KB Output is correct
57 Correct 641 ms 59172 KB Output is correct
58 Correct 575 ms 56420 KB Output is correct
59 Correct 535 ms 57296 KB Output is correct
60 Correct 575 ms 59900 KB Output is correct