QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#566008	#7726. Keys	Crysfly	AC ✓	296ms	38404kb	C++14	1.9kb	2024-09-15 22:52:40	2024-09-15 22:52:41

Judging History

你现在查看的是最新测评结果

[2024-09-15 22:52:41]
评测

测评结果：AC
用时：296ms
内存：38404kb

查看

[2024-09-15 22:52:40]
提交

answer

///////////////////////////////
#include <bits/stdc++.h>
using i64 = long long;
constexpr int S = 2e7;
struct seg {
	int ls[S], rs[S], cnt[S];
	int tot;
	int copy(int u){
		int v = ++ tot;
		ls[v] = ls[u], rs[v] = rs[u], cnt[v] = cnt[u];
		return v;
	}
	void update(int &u, int l, int r, int p, int w) {
		u = copy(u);
		cnt[u] += w;
		// std::cout << u << ' ' << l << ' '<< r << ' ' << cnt[u] << std::endl;
		if(l == r) return ;
		int mid = l + r >> 1;
		p <= mid ? update(ls[u], l, mid, p, w) : update(rs[u], mid + 1, r, p, w);
	}
	int query(int u, int l, int r, int p) {
		// std::cout << u << ' ' << l << ' '<< r << ' ' << cnt[u] << std::endl;
		if(!u) return 0;
		if(p <= l) return cnt[u];
		int mid = l + r >> 1;
		if(p <= mid) return query(ls[u], l, mid, p) + query(rs[u], mid + 1, r, p);
		else return query(rs[u], mid + 1, r, p);
	}
}ds;
int main() {
	// freopen("in.txt", "r", stdin);
	std::ios::sync_with_stdio(false);
	int n, k;
	std::cin >> n >> k;
	std::vector<i64> a(n), b(n);
	for(int i = 0; i < n; i ++) {
		std::cin >> a[i];
		b[-- a[i]] = i;
	}
	std::vector<std::vector<int>> upd1(n), upd2 = upd1;
	i64 ans = 0;
	for(int i = 1; i < n; i ++) {
		int last = b[i - 1];
		int cur = b[i];
		if(cur > last) {
			upd1[cur].emplace_back(last);
		} else {
			upd2[last].emplace_back(cur);
			ans ++;
		}
	}
	std::vector<int> rt(n);
	for(int i = 0; i < n; i ++) {
		if(i) rt[i] = rt[i - 1];
		for(auto p : upd1[i]) {
			ds.update(rt[i], 0, n - 1, p, 1);
		}
		for(auto p : upd2[i]) {
			ds.update(rt[i], 0, n - 1, p, -1);
		}
	}
	std::cout << 1ll * ans * n + b[n - 1] + 1 << std::endl;
	for(int i = 0; i < k; i ++) {
		int l, r;
		std::cin >> l >> r;
		l --, r --;
		int res = ans + ds.query(rt[r], 0, n - 1, l);
		int last = b[n - 1];
		if(l <= last && last <= r) last = l + r - last;
		std::cout << 1ll * res * n + last + 1 << std::endl;
	}
	return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3888kb

input:

output:

4
8
13

result:

ok answer is correct

Test #2:

score: 0

Accepted

time: 0ms

memory: 3536kb

input:

output:

result:

ok answer is correct

Test #3:

score: 0

Accepted

time: 1ms

memory: 3892kb

input:

output:

result:

ok answer is correct

Test #4:

score: 0

Accepted

time: 1ms

memory: 3648kb

input:

output:

result:

ok answer is correct

Test #5:

score: 0

Accepted

time: 1ms

memory: 3888kb

input:

output:

result:

ok answer is correct

Test #6:

score: 0

Accepted

time: 1ms

memory: 3540kb

input:

6 6
5 3 2 4 6 1
2 4
2 4
2 3
3 6
2 3
4 6

output:

result:

ok answer is correct

Test #7:

score: 0

Accepted

time: 1ms

memory: 3688kb

input:

7 7
1 5 7 2 6 3 4
2 7
2 6
5 6
2 3
3 4
2 6
3 4

output:

result:

ok answer is correct

Test #8:

score: 0

Accepted

time: 1ms

memory: 3596kb

input:

8 8
2 4 3 5 6 8 7 1
3 5
2 5
4 7
4 8
1 5
3 7
3 4
4 6

output:

result:

ok answer is correct

Test #9:

score: 0

Accepted

time: 0ms

memory: 3596kb

input:

9 9
5 9 7 8 6 4 1 2 3
1 6
3 5
6 9
3 8
6 7
3 8
2 3
4 6
5 7

output:

result:

ok answer is correct

Test #10:

score: 0

Accepted

time: 1ms

memory: 3664kb

input:

10 10
2 3 8 5 6 4 9 1 10 7
3 5
3 5
6 7
4 10
1 4
2 4
6 7
7 9
1 2
2 4

output:

result:

ok answer is correct

Test #11:

score: 0

Accepted

time: 1ms

memory: 3620kb

input:

16 17
6 12 2 8 16 9 13 4 7 11 5 15 10 14 1 3
9 15
7 11
7 11
9 12
11 12
11 16
7 14
3 7
10 13
13 16
1 15
3 15
6 8
1 14
8 15
10 12
5 9

output:

result:

ok answer is correct

Test #12:

score: 0

Accepted

time: 0ms

memory: 3592kb

input:

24 24
9 19 13 7 15 24 22 23 10 21 8 11 5 12 2 3 20 4 16 18 6 17 14 1
16 21
10 18
11 14
10 21
1 16
15 20
6 20
6 11
21 22
5 8
7 9
9 20
10 21
11 12
9 11
9 16
1 5
4 7
4 10
11 17
6 16
1 3
16 24
14 24

output:

result:

ok answer is correct

Test #13:

score: 0

Accepted

time: 1ms

memory: 3824kb

input:

38 39
9 6 20 31 21 28 38 25 16 7 26 30 3 33 14 24 29 13 37 8 10 22 32 27 35 23 19 4 12 34 18 15 5 36 1 11 17 2
16 31
16 19
16 33
5 7
7 20
21 34
5 6
1 28
7 22
16 34
5 34
11 31
4 31
9 12
18 31
33 38
1 8
20 35
13 36
2 29
30 34
7 15
18 34
22 23
7 12
28 35
6 11
13 26
22 36
14 16
1 9
17 26
3 11
18 26
10 2...

output:

result:

ok answer is correct

Test #14:

score: 0

Accepted

time: 1ms

memory: 3600kb

input:

60 64
17 60 58 49 24 55 4 44 22 14 52 30 5 20 18 16 32 46 28 12 34 1 27 54 9 43 45 21 7 51 47 23 40 37 19 59 48 39 10 33 2 35 56 41 38 26 15 36 3 25 8 6 57 11 42 53 13 50 29 31
24 45
3 8
37 55
11 45
31 55
26 53
27 59
27 28
19 54
9 20
5 11
18 37
8 37
16 54
3 20
18 36
9 42
14 48
7 44
29 50
39 48
45 55...

output:

result:

ok answer is correct

Test #15:

score: 0

Accepted

time: 1ms

memory: 3612kb

input:

86 96
56 25 57 21 85 46 10 61 39 74 33 6 66 81 20 52 68 40 78 8 31 42 53 70 43 77 71 34 4 11 76 12 37 64 29 86 45 44 35 15 1 27 84 58 22 18 48 82 83 19 65 62 54 38 32 26 13 3 36 60 79 30 28 75 5 41 16 69 24 72 80 9 63 23 7 50 14 17 67 2 51 73 59 49 55 47
45 69
21 30
41 49
21 24
2 23
15 70
22 61
19 5...

output:

result:

ok answer is correct

Test #16:

score: 0

Accepted

time: 1ms

memory: 3876kb

input:

122 149
90 116 40 16 104 6 66 76 7 14 36 110 70 89 79 29 34 107 96 26 39 8 57 91 46 12 88 102 84 18 37 19 33 108 4 17 62 1 78 77 105 118 53 51 54 10 30 48 109 99 25 67 83 59 119 121 94 97 45 114 32 56 115 41 93 85 64 73 80 42 120 31 71 55 58 63 82 81 86 87 43 74 95 9 65 100 21 72 22 15 113 23 38 50 ...

output:

result:

ok answer is correct

Test #17:

score: 0

Accepted

time: 2ms

memory: 3700kb

input:

208 232
205 186 84 91 3 61 80 62 96 146 32 124 113 5 172 73 23 188 131 74 153 102 107 51 48 47 155 154 150 163 86 132 182 90 180 144 52 26 34 148 117 36 70 171 30 100 177 178 12 192 65 175 201 81 158 142 119 200 18 79 66 168 76 206 50 174 152 197 123 59 138 63 118 6 71 57 28 195 29 99 104 33 49 109 ...

output:

result:

ok answer is correct

Test #18:

score: 0

Accepted

time: 0ms

memory: 3728kb

input:

328 350
40 254 102 26 76 30 188 183 281 148 19 91 151 83 21 182 103 214 142 23 111 105 131 126 233 13 89 116 266 167 5 231 17 85 219 179 169 285 121 43 36 228 101 114 35 109 324 213 20 130 296 321 159 308 224 4 46 250 207 277 221 42 328 203 271 12 44 202 310 14 161 157 16 93 177 226 146 18 150 222 2...

output:

result:

ok answer is correct

Test #19:

score: 0

Accepted

time: 3ms

memory: 3800kb

input:

537 542
269 163 8 446 352 236 138 506 257 181 442 516 148 458 219 72 95 49 206 200 14 229 527 515 60 133 366 245 233 477 532 216 468 357 417 536 223 470 266 327 530 208 141 523 277 78 330 272 312 101 161 151 186 204 289 313 170 226 187 514 372 275 178 116 20 421 424 244 326 413 513 293 300 239 315 4...

output:

result:

ok answer is correct

Test #20:

score: 0

Accepted

time: 4ms

memory: 3792kb

input:

918 888
671 349 306 533 826 65 514 247 579 612 709 616 369 387 7 567 545 254 360 899 368 554 53 11 570 489 416 185 441 329 900 275 560 903 327 803 812 32 506 585 756 688 683 356 448 770 513 334 64 798 917 799 573 242 450 586 302 876 337 427 695 750 657 46 357 641 90 77 651 908 741 713 414 843 701 43...

output:

result:

ok answer is correct

Test #21:

score: 0

Accepted

time: 7ms

memory: 5980kb

input:

1505 1465
960 253 417 1194 423 621 375 1256 50 223 944 1119 465 459 16 816 1178 945 795 1337 340 471 712 361 172 1440 67 984 546 39 836 1471 528 493 993 311 871 312 620 1422 1070 300 1124 248 84 617 406 1265 308 892 1054 1195 288 872 1081 864 1049 524 46 681 587 1144 239 1150 1219 1008 622 1258 912 ...

output:

result:

ok answer is correct

Test #22:

score: 0

Accepted

time: 3ms

memory: 4248kb

input:

2453 2519
67 1702 1204 2352 750 155 492 359 1808 1295 1467 1074 1028 1888 326 1254 2011 2321 304 1650 450 2142 1318 2261 100 879 422 524 2150 1098 103 889 1857 2182 241 167 2185 1032 2447 436 129 22 1486 1430 1956 2088 2174 2167 1651 615 1465 1972 1043 2025 638 944 1039 339 872 1265 2259 1832 1448 1...

output:

result:

ok answer is correct

Test #23:

score: 0

Accepted

time: 21ms

memory: 6544kb

input:

4219 4383
279 880 236 3804 617 940 2584 4078 3200 3884 2188 3964 759 3745 1546 1961 3687 941 2440 3932 3869 1730 4176 945 1451 633 2497 3560 3395 3046 72 788 1268 1393 793 2632 1591 1007 837 1612 4114 2057 1186 130 1706 3272 3281 3634 2647 1333 904 1479 977 1445 3407 2122 2874 2048 1118 120 1484 594...

output:

result:

ok answer is correct

Test #24:

score: 0

Accepted

time: 11ms

memory: 4904kb

input:

6455 7056
3567 3927 6326 3640 2317 6257 4266 3138 4071 3469 1739 5528 1312 1118 5844 5802 2182 6269 1509 4363 1291 4943 1590 4720 1039 2070 966 925 5097 5161 232 650 5071 5389 4573 1408 1440 3642 527 5049 165 6354 218 2467 3325 4008 4473 5998 4605 3897 5282 268 6026 1690 1014 1603 4003 1550 5597 764...

output:

result:

ok answer is correct

Test #25:

score: 0

Accepted

time: 22ms

memory: 9852kb

input:

11231 12206
10556 5075 298 11069 8558 1246 211 124 8132 1208 8151 827 6075 5384 4837 4135 9827 7733 4912 2844 2804 7684 9463 9461 9986 2226 2848 10183 5824 6492 4806 7909 10025 6122 1456 2502 4227 2955 1913 1653 6148 5899 4085 10695 9259 6068 5095 3560 10152 5558 9067 9151 6845 8432 10055 7931 1125 ...

output:

result:

ok answer is correct

Test #26:

score: 0

Accepted

time: 42ms

memory: 8844kb

input:

16509 19529
2201 453 7 13250 15531 3835 9734 5484 2404 8357 12928 5637 14780 5546 1167 663 10865 2650 70 3486 2604 11364 4066 1714 4105 12700 929 16316 12449 8977 2375 1277 14791 14045 607 3481 10674 8614 1050 4926 12243 3376 2633 8782 1389 14833 7070 13612 12245 14956 5077 6465 16239 10974 7720 728...

output:

result:

ok answer is correct

Test #27:

score: 0

Accepted

time: 49ms

memory: 10724kb

input:

24598 31832
5370 21217 11612 6774 9675 23859 18633 12046 20835 20469 13419 21896 16800 4857 19211 7106 21175 23548 8368 7000 16408 16754 21193 5213 9597 11740 23533 2378 3423 20007 8866 19939 3968 8250 23769 1415 17745 21062 6133 7765 1038 22056 21130 6718 13720 17651 3000 8271 1541 21340 10321 3621...

output:

result:

ok answer is correct

Test #28:

score: 0

Accepted

time: 97ms

memory: 18904kb

input:

38126 51886
28646 3858 9748 4972 7714 3785 1391 36263 35708 18650 13714 28644 27840 1524 32825 22374 16584 37104 26712 23002 7670 9070 10625 20517 28298 10535 7140 913 24602 18002 30123 20033 24225 32738 34645 19113 1736 37392 22061 11387 1546 15851 25686 356 10202 26025 21684 18691 3999 1964 4140 2...

output:

result:

ok answer is correct

Test #29:

score: 0

Accepted

time: 153ms

memory: 24116kb

input:

59476 87687
56193 27891 2785 44865 39533 47342 54843 8562 49860 6605 10140 23267 24383 33067 52528 42410 38284 28854 21270 14388 44549 20799 11729 7704 30899 39416 25066 37058 55634 12726 22195 55765 9622 39505 508 12491 38690 59239 25545 45697 848 29093 40541 43964 27271 59435 32963 57783 51673 330...

output:

result:

ok answer is correct

Test #30:

score: 0

Accepted

time: 244ms

memory: 32412kb

input:

90403 100000
20761 83266 77008 88162 83308 17507 79968 25465 51592 36692 67821 4431 47829 75528 27794 6958 89160 31877 17536 84971 88430 54524 9932 17648 5287 28900 66828 8415 64944 24484 4748 44529 53870 55473 27734 53254 69287 40079 57920 37040 12487 77900 6758 75618 72400 33902 70946 73976 47354 ...

output:

result:

ok answer is correct

Test #31:

score: 0

Accepted

time: 231ms

memory: 37676kb

input:

100000 100000
95768 45802 85621 42068 98814 80827 1515 65715 91561 98857 22264 37729 9291 22282 28846 63891 29077 78149 87336 6003 81659 26344 39792 43908 52915 93428 62136 68841 51689 83268 11797 79037 60832 30679 7611 43889 60815 45198 5923 43862 67038 62189 8550 8501 69685 18487 34403 23232 1975 ...

output:

result:

ok answer is correct

Test #32:

score: 0

Accepted

time: 283ms

memory: 36192kb

input:

100000 100000
75352 70114 7146 73089 71352 66150 54502 5126 84701 80707 72479 55416 50482 37794 20616 19445 45607 23385 85231 20600 38110 1384 72007 65163 63029 47730 24866 15148 49596 63559 78012 78639 57455 99092 28582 99664 9855 41337 40541 56487 67232 29511 44574 90818 93898 42682 27293 55612 17...

output:

result:

ok answer is correct

Test #33:

score: 0

Accepted

time: 271ms

memory: 37348kb

input:

100000 100000
32565 28016 72193 81208 82306 60875 82367 15326 74428 35201 14062 21048 69222 69007 83359 22037 33237 1164 51899 85710 40624 22715 42885 3134 15518 61319 41528 52781 45729 23423 11846 59429 1890 62197 15591 93418 43072 73259 94408 86288 19195 62258 48701 29956 73064 3147 16019 26598 68...

output:

result:

ok answer is correct

Test #34:

score: 0

Accepted

time: 254ms

memory: 36972kb

input:

100000 100000
72858 95643 92491 96220 75545 10222 97268 35420 7049 37207 62007 41583 9806 2981 69962 82590 35036 27353 19021 61813 50390 1303 61938 63861 25813 75969 96175 16936 65959 49582 70188 47622 5813 10587 39946 29369 79043 83277 27219 63043 81542 84157 59959 73446 28817 58143 41819 75747 447...

output:

result:

ok answer is correct

Test #35:

score: 0

Accepted

time: 296ms

memory: 37504kb

input:

100000 100000
82610 55325 47559 16943 35724 52309 35033 69131 91534 25883 67776 49927 65878 13274 71935 84026 89657 81159 31086 78835 29999 79695 28706 62221 51834 503 15226 9310 65853 40080 36519 47635 59051 48111 14439 55712 82332 37078 51667 91439 67641 22194 79435 68774 91505 91622 10577 64896 4...

output:

result:

ok answer is correct

Test #36:

score: 0

Accepted

time: 134ms

memory: 37480kb

input:

100000 100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

result:

ok answer is correct

Test #37:

score: 0

Accepted

time: 130ms

memory: 37520kb

input:

100000 100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

result:

ok answer is correct

Test #38:

score: 0

Accepted

time: 152ms

memory: 36136kb

input:

100000 100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

result:

ok answer is correct

Test #39:

score: 0

Accepted

time: 138ms

memory: 36716kb

input:

100000 100000
100000 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 99969 99968 99967 99966 99965 99964 99963 99962 99961 99960 99959 99958 99957 99956 99955 99954 999...

output:

result:

ok answer is correct

Test #40:

score: 0

Accepted

time: 146ms

memory: 38188kb

input:

100000 100000
32371 22130 59896 60223 64059 30936 71580 51165 85969 17378 97170 10696 21913 7578 95745 36087 59578 96089 32206 77313 24248 22397 11071 79732 20720 22811 64823 15861 50365 7448 4734 50369 63155 1438 49794 47257 71607 231 58010 90976 39558 3754 84884 83644 88780 70552 65089 44605 2704 ...

output:

result:

ok answer is correct

Test #41:

score: 0

Accepted

time: 106ms

memory: 38404kb

input:

100000 100000
100000 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 99969 99968 99967 99966 99965 99964 99963 99962 99961 99960 99959 99958 99957 99956 99955 99954 999...

output:

result:

ok answer is correct