Submission #455116

#	Time	Username	Problem	Language	Result	Execution time	Memory
455116		_adis	Pilot (NOI19_pilot)	C++14	100 / 100	641 ms	59900 KiB

pilot

/*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 (stderr)

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

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11