QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #263796 | #7771. 不是这一道据数构结题 | ucup-team1004# | 0 | 51ms | 8064kb | C++14 | 915b | 2023-11-25 08:03:21 | 2024-07-04 03:08:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#ifdef DEBUG
template<class T>
ostream& operator << (ostream &out,vector<T> a){
out<<'[';
for(T x:a)out<<x<<',';
return out<<']';
}
template<class T>
vector<T> ary(T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<class T>
void debug(T x){
cerr<<x<<endl;
}
template<class T,class...S>
void debug(T x,S...y){
cerr<<x<<' ',debug(y...);
}
#else
#define debug(...) void()
#endif
const int N=1e6+10;
int n,m,a[N],pre[N],suf[N];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
if(n*m>2e8)return 0;
for(int l,r;m--;){
scanf("%d%d",&l,&r);
pre[l-1]=suf[r+1]=n+1;
for(int i=l;i<=r;i++)pre[i]=min(pre[i-1],a[i]);
for(int i=r;i>=l;i--)suf[i]=min(suf[i+1],a[i]);
int ans=0;
for(int i=l;i<=(l+r)/2;i++)ans+=pre[i]==a[i];
printf("%d\n",(r-l+1)-ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 7924kb
input:
100 100 57 39 73 88 98 3 54 10 63 31 96 22 94 53 99 66 7 90 29 27 91 37 74 4 64 43 86 100 12 58 78 97 75 87 36 51 40 20 48 92 26 72 89 85 46 13 55 80 6 47 41 17 30 25 60 35 93 28 69 16 83 23 1 34 56 45 18 21 38 11 68 71 8 2 84 76 15 33 44 81 77 82 70 24 67 95 61 9 32 49 50 65 19 59 5 42 14 62 52 79 ...
output:
63 89 15 7 9 1 52 19 1 10 44 7 3 12 5 33 9 84 2 51 32 0 42 63 43 18 3 27 39 22 47 49 29 17 32 34 34 6 52 37 15 2 9 3 38 84 44 7 2 32 15 78 13 57 16 56 45 8 66 37 12 76 46 51 11 28 77 6 4 64 34 18 5 33 26 35 40 3 7 16 13 15 34 57 61 44 29 10 7 16 20 60 46 0 36 44 1 22 6 0
result:
wrong answer 1st numbers differ - expected: '65', found: '63'
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 8004kb
input:
100 100 2 3 1 3 3 8 1 1 1 3 2 3 2 75 1 44 78 3 3 65 2 1 3 3 90 2 1 1 1 2 2 2 1 2 9 3 24 1 2 1 89 2 2 42 2 66 1 1 19 25 3 2 3 2 3 51 1 1 3 1 3 29 21 2 2 2 1 2 1 3 3 2 84 2 1 11 2 2 3 2 9 1 1 1 1 99 48 1 77 3 9 78 69 1 2 1 1 2 1 2 21 68 41 76 9 76 7 43 30 81 45 84 81 83 23 45 57 91 17 65 72 81 39 91 3...
output:
40 28 59 32 44 34 1 16 30 38 7 46 39 7 55 30 55 32 40 62 11 6 38 13 62 27 57 68 13 66 59 29 7 32 27 4 30 57 15 16 68 33 24 57 58 6 7 59 10 30 11 11 30 27 31 19 31 61 30 20 6 53 46 3 50 38 69 60 31 26 51 14 21 32 20 4 9 1 3 41 2 15 80 49 23 8 15 15 69 9 15 30 54 47 35 53 59 29 7 65
result:
wrong answer 1st numbers differ - expected: '35', found: '40'
Test #3:
score: 0
Wrong Answer
time: 6ms
memory: 7928kb
input:
3000 3000 82 1139 2770 344 363 880 427 2001 207 2969 1309 2063 2349 1817 1869 2724 2380 1887 1377 1422 1732 449 2105 1706 1155 2417 963 308 1996 2788 737 1963 1973 1163 2899 2438 760 1995 1435 1750 1947 2863 1606 1078 493 2922 1478 607 1871 2191 2978 2587 1699 332 1581 2048 68 350 2220 1306 1633 187...
output:
1454 903 1094 247 2567 10 1172 324 1706 2218 621 42 1346 1446 631 2739 1014 822 629 603 986 1101 1125 1183 146 2254 972 979 630 1095 683 2312 1882 159 1151 1105 1671 781 723 2038 474 329 977 879 2079 5 1255 975 611 1045 1373 1499 1814 1153 1166 595 647 292 20 168 2601 1651 1970 1657 1035 1130 153 47...
result:
wrong answer 1st numbers differ - expected: '1464', found: '1454'
Test #4:
score: 0
Wrong Answer
time: 6ms
memory: 7924kb
input:
3000 3000 2120 271 658 684 1092 795 2522 2924 2204 382 709 1351 2977 1639 1190 2472 458 1337 1034 566 2644 664 1224 1410 1820 625 2203 2045 1979 2297 2926 1238 2014 1492 1372 2594 1324 1854 1968 1074 919 2345 1544 1880 626 2505 1742 1427 2892 99 447 1732 2273 2490 1166 2419 2717 1248 2493 1048 2291 ...
output:
1073 879 1827 55 330 99 2417 575 1201 1583 476 1115 2738 1541 1241 55 1396 1040 823 266 455 859 244 1294 1817 275 220 1043 2441 1173 2454 418 798 74 364 844 871 1004 414 986 718 444 340 2523 379 1156 2683 253 23 208 1695 797 42 1075 333 3 5 112 1642 1869 683 733 69 401 2422 776 461 1286 2051 749 108...
result:
wrong answer 1st numbers differ - expected: '1079', found: '1073'
Test #5:
score: 0
Wrong Answer
time: 6ms
memory: 8052kb
input:
3000 3000 2637 1681 2145 1131 33 618 2714 914 2587 2182 1823 1044 1320 2020 568 2 411 902 523 2075 910 459 124 669 1546 2593 1314 312 2736 1408 1578 28 291 1017 421 798 2202 978 597 2246 1349 1486 2756 2464 1912 636 1130 201 648 882 2737 2066 2007 1758 91 2923 49 1288 2254 776 2814 1315 1665 2306 25...
output:
705 472 1001 1838 192 1481 1272 2297 84 1732 2233 297 257 852 1431 2479 1692 864 1633 332 1066 724 371 26 857 1507 1474 232 365 1478 89 774 173 164 950 1528 805 1214 134 1463 571 547 439 103 25 2105 1457 1250 1262 260 9 223 581 1433 1790 1895 172 953 1411 1294 568 502 1602 976 436 1560 649 2447 115 ...
result:
wrong answer 1st numbers differ - expected: '708', found: '705'
Test #6:
score: 0
Wrong Answer
time: 6ms
memory: 7960kb
input:
3000 3000 15 64 32 83 23 22 48 7 68 36 43 75 29 17 37 97 92 42 50 87 73 43 12 48 83 44 1 13 23 96 48 60 99 26 2 104 73 73 64 61 64 49 67 94 89 9 96 102 66 19 95 2 29 78 102 61 77 84 34 92 36 31 44 25 68 47 137 131 75 37 21 173 62 44 36 53 19 165 98 100 95 57 85 32 87 69 118 85 24 35 36 98 47 44 92 2...
output:
466 718 422 446 1171 1807 582 772 626 665 1075 876 2827 511 1179 292 2022 378 1924 1477 506 2129 467 1296 402 1176 352 489 404 921 1254 22 33 1689 290 1732 833 557 2529 214 859 988 701 713 4 2277 262 58 163 657 887 27 1049 2197 649 1211 428 1834 562 2192 894 1421 115 1906 1690 532 13 2139 2555 1380 ...
result:
wrong answer 1st numbers differ - expected: '467', found: '466'
Test #7:
score: 0
Wrong Answer
time: 6ms
memory: 8012kb
input:
3000 3000 96 48 34 1 27 93 76 3 38 26 79 74 25 95 34 37 5 26 54 37 62 22 17 3 53 34 10 132 64 91 53 34 74 92 64 3 103 38 74 40 31 38 63 12 84 84 80 5 88 22 51 66 28 158 16 31 26 53 47 22 66 89 7 65 91 49 62 73 26 54 13 33 28 45 48 90 91 46 37 34 53 69 70 52 62 71 56 190 154 72 25 6 17 196 66 39 80 5...
output:
1492 787 352 120 296 1007 779 340 652 374 1872 529 302 1483 2308 207 1098 1064 1366 894 1235 1835 1690 62 630 179 914 1719 741 725 297 343 1634 46 62 104 1688 1265 1961 907 1343 354 176 157 119 1855 1783 1228 130 361 766 1500 1634 330 217 54 1124 1638 847 1333 464 262 925 251 920 2233 1770 218 97 10...
result:
wrong answer 1st numbers differ - expected: '1486', found: '1492'
Test #8:
score: 0
Wrong Answer
time: 6ms
memory: 8064kb
input:
3000 3000 24 75 55 19 9 74 4 22 81 77 75 46 60 50 19 50 1 41 8 63 4 47 93 24 105 16 28 76 18 96 1 68 46 80 41 83 78 36 88 45 83 54 67 46 94 99 44 61 14 50 143 97 95 78 8 92 36 59 95 26 67 23 26 95 77 92 98 13 63 149 129 61 74 39 38 55 15 90 48 3 37 39 100 77 18 10 19 10 20 77 71 46 65 84 46 7 175 81...
output:
1579 101 35 1427 1138 1137 7 159 187 1880 486 1145 1417 1525 1 1447 291 622 741 657 2326 527 506 53 339 15 975 276 1044 13 46 1100 631 338 534 2103 629 234 104 79 722 723 1225 493 1637 1415 1781 591 210 153 108 2013 676 2391 1470 1979 723 550 1515 261 62 831 746 2599 826 1257 338 1953 2113 314 2148 ...
result:
wrong answer 1st numbers differ - expected: '1585', found: '1579'
Test #9:
score: 0
Wrong Answer
time: 48ms
memory: 7948kb
input:
10000 10000 1225 3839 1022 812 2195 8154 9848 3399 6401 5375 4192 5933 7758 9460 5569 6817 1504 104 7537 509 3830 3790 686 416 5452 4214 2651 2825 5881 4373 2118 8244 8803 5866 1737 5206 3037 4862 5976 2871 9541 6867 2024 8451 7815 1083 5523 8874 1745 828 8022 5706 3404 651 4212 8126 2555 6660 5481 ...
output:
2312 3594 3089 8530 190 955 792 3051 2029 2017 1535 2185 2825 762 5555 4423 1296 2060 252 3471 6748 2222 3438 79 8988 3652 6005 6239 591 6580 3461 5984 781 2670 4608 3812 6495 5401 5628 3382 8478 3395 4100 758 3375 2552 1635 447 3100 2311 6116 1225 6208 120 319 1888 2076 760 1639 951 6462 4070 538 2...
result:
wrong answer 1st numbers differ - expected: '2317', found: '2312'
Test #10:
score: 0
Wrong Answer
time: 48ms
memory: 7948kb
input:
10000 10000 4293 5943 4058 5440 7413 5250 1171 9947 4399 9939 5300 6419 5446 2275 8834 6841 1566 3814 2298 5294 8131 603 2736 4135 946 7071 3233 6196 6458 5162 8229 3087 227 828 7544 3423 7594 4496 8790 4052 8704 3088 7330 7269 5010 9400 9399 3819 302 4258 2985 3323 6455 5755 7489 321 501 3299 2026 ...
output:
2264 2646 438 7134 3422 85 4842 1480 1879 8432 6847 8563 4631 788 3686 244 3897 1321 234 5379 5852 7992 862 931 3318 9294 3506 5276 2640 4539 248 3219 178 7164 7696 2802 2139 335 6977 2385 4365 5376 3226 3580 5476 4811 1357 1051 2118 2858 1450 1480 1419 2597 1071 5956 2389 3952 3389 34 207 859 2759 ...
result:
wrong answer 1st numbers differ - expected: '2271', found: '2264'
Test #11:
score: 0
Wrong Answer
time: 51ms
memory: 8036kb
input:
10000 10000 7 178 96 109 117 3 170 302 209 84 248 310 97 70 222 255 276 127 233 219 109 282 8 182 20 128 75 158 39 214 102 260 13 80 276 221 271 319 129 110 72 89 254 45 34 322 310 299 305 32 93 224 5 261 126 140 311 81 100 72 328 312 42 16 231 146 72 238 178 178 179 226 314 152 167 202 295 258 15 2...
output:
3534 3486 6388 272 972 2113 804 3962 2803 7 248 1426 9068 2833 5794 4713 5142 4189 1817 2031 398 5453 6140 2810 4763 3122 22 2006 94 827 4165 4457 308 3861 9007 7829 2107 1765 7994 649 3278 1354 8578 1737 4746 5971 131 5246 3416 857 6272 845 1844 8034 1741 1700 1451 3918 4336 969 1335 3139 4965 4550...
result:
wrong answer 1st numbers differ - expected: '3540', found: '3534'
Test #12:
score: 0
Wrong Answer
time: 51ms
memory: 8044kb
input:
10000 10000 3 31 195 326 322 174 300 177 87 56 74 14 39 240 134 249 176 187 87 118 177 304 269 44 128 328 112 121 96 93 140 163 209 271 29 296 232 309 228 183 238 100 66 118 204 90 156 45 204 126 232 68 318 327 5 3 153 331 180 62 308 172 175 142 88 318 236 75 276 251 67 218 28 118 141 257 65 151 183...
output:
1090 1583 3512 1025 6204 8319 2859 5732 1093 2341 639 2482 466 1124 3819 6087 619 2971 3760 392 3683 3744 4699 6416 4519 8135 6120 411 1498 1250 1161 5093 391 4416 1597 6346 4453 3974 4619 5331 3838 1090 182 4341 9158 1897 9171 205 510 2404 2281 9308 2464 3200 1893 2252 5593 1247 1523 556 7395 2490 ...
result:
wrong answer 1st numbers differ - expected: '1097', found: '1090'
Test #13:
score: 0
Wrong Answer
time: 12ms
memory: 7720kb
input:
200000 200000 120536 165588 195015 67563 60504 93355 188680 98879 30412 35909 162690 193085 79065 58869 51576 146413 166618 182838 56146 110147 142857 111033 186246 180779 63081 24777 52683 191278 98735 11504 115999 116939 157422 109468 175004 10755 112531 71163 35398 71262 141229 231 123311 168965 ...
output:
result:
wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements
Test #14:
score: 0
Wrong Answer
time: 11ms
memory: 5872kb
input:
200000 200000 5203 2776 2051 83 5255 4479 6328 3395 5764 3079 4020 4235 31 62 2282 1983 4052 5141 6514 108 45 84 2874 2225 5833 2277 5069 777 3458 4312 6577 1083 18 6003 4773 1935 2908 91 843 5317 6643 103 5581 113 6234 3738 144 3953 1234 396 4543 3518 5508 1833 1674 1446 1134 6455 4343 558 658 3664...
output:
result:
wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements
Test #15:
score: 0
Wrong Answer
time: 11ms
memory: 7796kb
input:
200000 200000 5102 3159 748 5427 621 5896 499 5528 1847 6008 961 3084 1541 3370 3477 6551 3122 34 60 5045 1000 2091 119 35 345 92 47 6200 2305 611 27 20 4462 37 1192 108 5020 6490 5834 2997 6615 4662 102 4466 3073 634 2393 278 6122 6451 4679 4161 2316 2074 4859 782 3340 3997 6350 6659 4747 2199 5225...
output:
result:
wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements
Test #16:
score: 0
Wrong Answer
time: 11ms
memory: 5768kb
input:
200000 200000 5620 4596 1787 1569 11 3679 57 5561 1635 5384 5280 71 127 4084 4074 4 3533 4939 5115 96 336 75 3997 951 133 6410 4574 3466 3102 534 6321 107 2300 2531 5426 73 20 12 101 607 10 4424 5847 134 6212 862 855 5070 77 91 2010 4014 4678 4050 3695 3451 2790 4235 2235 5998 6354 5149 4794 4789 40...
output:
result:
wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements
Test #17:
score: 0
Time Limit Exceeded
input:
1000000 1000000 87382 651796 951220 648926 497665 375383 228684 303780 166986 89826 91242 258504 374341 653338 160191 648153 603954 860894 376629 474180 967487 270337 3022 832849 628198 269953 992793 314447 701562 440916 559722 134912 67124 636002 748016 771119 200861 655997 618755 558 882633 709234...
output:
401381 115083 693935 405914 741542 92619 200482 82744 151383 227993 301558 510446 34236 128588 315008 504002 716089 46099 145047 544849 118905 145548 413032 596746 100847 50885 883794 180188 311835 417202 651476 188579 70432 122234 276152 104237 150057 733178 335324 609186 51877 907237 408506 507195...
result:
Test #18:
score: 0
Time Limit Exceeded
input:
1000000 1000000 3228 19 1838 21 15231 54 27226 18805 16744 57 25133 23568 27304 24323 9187 89 14287 13412 20542 21860 23602 65 1 32705 27 20439 19966 70 7865 13967 127 30379 34 95 12820 8224 14188 32692 93 29481 28113 14591 119 7443 2802 6678 51 6838 88 74 7855 95 775 11917 104 18776 34 22985 32134 ...
output:
601769 87969 543630 148199 122243 85809 8151 181375 13898 194231 213320 139427 173146 498608 268378 595803 407079 147632 107019 14133 345523 160959 75771 611037 108835 263596 11061 517130 545492 707800 287948 26597 639826 4456 247017 426978 139144 21845 357753 297208 695756 93724 571702 513895 14232...
result:
Test #19:
score: 0
Time Limit Exceeded
input:
1000000 1000000 13910 7760 24228 1793 79 14626 44 10663 25005 56 4240 15833 3609 19816 13269 28175 8807 67 1480 27123 69 12868 11829 3 18390 5510 58 28157 26708 17269 10176 14025 41 7746 12814 9220 24534 115 12446 51 6256 21293 28779 6845 31048 19928 19877 13972 13317 7203 9974 13131 133 13 5348 166...
output:
149900 626053 592271 104647 180033 665731 132494 790578 318320 111434 27217 177440 318890 202107 522916 250070 266049 306155 869701 340279 43423 690070 490518 148535 558728 328407 440521 667770 674164 327398 120938 251383 476733 316590 798068 255030 307450 809190 159182 146502 692622 450092 677096 2...
result:
Test #20:
score: 0
Time Limit Exceeded
input:
1000000 1000000 15899 2139 32955 19636 21943 29782 28207 9095 20266 68 15471 14533 17782 21804 31540 21751 19168 15466 19302 34 24617 3544 66 31466 31516 3341 30147 6947 26716 135 11544 50 30167 5 11 7820 149 5146 32617 20175 23019 23260 8830 16538 88 2357 22200 21845 2144 12436 104 31 24930 10455 1...
output:
127355 622405 88961 350100 62056 220806 468811 369343 696625 227026 194494 770540 698550 327849 58026 172049 19258 81492 11197 448622 621725 574031 298968 855976 21113 532363 932555 240258 256797 655253 96657 280053 640364 191903 328364 350240 422633 246026 781632 152841 111839 532528 705768 191458 ...