QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #250373 | #7771. 不是这一道据数构结题 | C1942huangjiaxu | 0 ✓ | 0ms | 0kb | C++14 | 1.5kb | 2023-11-13 07:57:08 | 2023-11-13 07:57:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
template<class rd>
void read(rd &x){
char c=getchar();
for(;c<48||c>57;c=getchar());
for(x=0;c>47&&c<58;c=getchar())x=(x<<1)+(x<<3)+(c^48);
}
int n,q,a[N],ans[N],st[N],tp,t[N],sz[N];
int tr[N],pl[N],pc[N];
vector<int>g[N],u[N];
vector<pair<int,int> >e[N];
void upd(int x,int v){
for(;x<=n;x+=x&-x)tr[x]+=v;
}
int sum(int x){
int res=0;
for(;x;x-=x&-x)res+=tr[x];
return res;
}
void init(){
st[tp=0]=n+1;
for(int i=n;i;--i){
while(a[st[tp]]>a[i])sz[tp]=0,--tp;
if(a[st[tp]]<a[i])++tp;
++sz[tp],st[tp]=i;
pl[i]=st[tp-1],pc[i]=sz[tp];
u[a[i]].push_back(i);
}
for(int i=n;i;--i){
for(auto v:u[i]){
int rk=sum(pl[v]-1)+pc[v];
int x=0;
for(int j=19;~j;--j){
if(x+(1<<j)<=n&&tr[x+(1<<j)]<rk){
x+=1<<j;
rk-=tr[x];
}
}
t[v]=x+1;
}
for(auto v:u[i])upd(v,1);
}
memset(tr,0,sizeof(tr));
}
int main(){
read(n),read(q);
for(int i=1;i<=n;++i)read(a[i]);
for(int i=1,l,r;i<=q;++i){
read(l),read(r);
e[l].push_back(make_pair(r,i));
}
init();
st[tp=0]=n+1;
for(int i=n;i;--i){
while(a[st[tp]]>a[i]){
for(auto v:g[tp]){
upd(t[v],-1);
upd(v,1);
}
g[tp].clear();
--tp;
}
upd(t[i],1);
if(a[st[tp]]<a[i])++tp;
st[tp]=i;
g[tp].push_back(i);
for(auto v:e[i])ans[v.second]=sum(v.first);
}
for(int i=1;i<=q;++i)printf("%d\n",ans[i]);
return 0;
}
詳細信息
Test #1:
score: 0
Time Limit Exceeded
input:
100 100 37 77 8 56 29 7 65 28 3 49 97 89 18 36 33 54 82 24 83 58 96 64 16 9 2 69 100 1 10 39 99 50 46 78 47 85 53 62 52 41 17 94 70 44 98 59 20 92 4 21 22 0 84 45 25 38 57 13 42 79 74 93 71 88 23 91 81 34 51 68 76 31 40 87 60 90 12 15 86 11 73 95 19 5 55 48 66 35 27 14 67 63 6 30 72 80 61 43 26 75 1...
output:
result:
Test #2:
score: 0
Time Limit Exceeded
input:
100 100 2 1 1 81 2 2 0 1 2 3 25 57 26 3 64 1 21 2 3 3 18 3 2 2 1 1 3 2 1 3 83 3 1 3 94 65 2 1 3 1 2 14 2 3 1 1 3 3 34 57 1 1 72 85 1 2 1 3 2 2 1 3 3 2 1 1 1 2 66 2 1 1 3 3 3 2 3 1 1 3 65 25 95 3 71 1 2 1 17 1 1 1 15 3 3 2 2 3 43 1 9 61 20 69 23 78 28 78 13 97 7 99 22 67 24 25 3 44 33 95 87 95 3 68 1...
output:
result:
Test #3:
score: 0
Time Limit Exceeded
input:
3000 3000 1435 2843 255 1028 1524 1189 918 2858 1259 1648 733 1885 2031 1261 524 685 2965 835 1017 2552 1220 507 139 2981 175 420 455 1203 1957 2487 1009 866 1321 2818 2022 2715 416 2169 2531 2724 1516 2919 581 2201 1049 463 2509 742 2094 937 1927 497 250 632 2900 2160 941 2761 2280 1348 991 2390 21...
output:
result:
Test #4:
score: 0
Time Limit Exceeded
input:
3000 3000 2333 2615 2997 210 430 1932 1734 2284 1018 153 2459 2849 1618 1221 2704 959 1853 831 2976 1236 1001 707 1586 535 1649 1641 2147 427 247 1410 267 1362 329 1408 1976 1003 2125 2027 1038 1154 1680 571 2634 166 1706 1381 1194 2889 2492 1036 759 1453 2894 857 59 2755 2329 1072 292 998 1961 789 ...
output:
result:
Test #5:
score: 0
Time Limit Exceeded
input:
3000 3000 1884 281 956 46 1601 645 1200 1015 933 1584 133 1761 1756 616 2888 2475 1664 1516 2642 2997 2124 1192 750 1928 1217 2481 707 522 1690 2949 948 1771 1994 2782 2232 461 2631 836 345 2222 2750 1540 2361 2759 230 813 1379 856 465 669 1366 2166 1888 2527 324 2324 1536 515 2394 2395 1014 2698 22...
output:
result:
Test #6:
score: 0
Time Limit Exceeded
input:
3000 3000 77 37 57 58 90 98 2 50 47 53 17 20 67 31 12 13 82 97 52 26 10 64 6 84 92 55 92 98 68 100 78 29 52 16 33 21 44 22 70 18 88 40 85 151 62 97 12 96 80 44 7 114 23 13 59 97 16 45 94 100 99 24 54 22 72 63 49 93 29 24 59 137 20 2 15 72 16 15 62 41 27 89 92 55 77 18 61 32 80 35 10 22 8 16 94 64 40...
output:
result:
Test #7:
score: 0
Time Limit Exceeded
input:
3000 3000 50 40 62 17 17 43 60 2 41 42 7 2 72 72 61 76 42 37 49 19 27 7 83 59 87 81 51 88 60 88 99 60 54 39 41 83 57 92 11 55 125 98 79 62 37 42 156 63 80 75 29 28 95 68 58 50 6 136 7 60 64 19 36 32 92 126 46 37 87 82 32 38 16 32 31 42 58 156 44 66 32 58 97 90 25 83 13 15 27 25 16 90 46 37 87 106 9 ...
output:
result:
Test #8:
score: 0
Time Limit Exceeded
input:
3000 3000 100 11 8 99 53 36 40 90 73 47 33 67 21 29 7 95 59 17 53 21 59 128 14 115 36 13 27 46 94 70 95 83 74 46 93 44 69 79 76 55 97 54 90 10 97 20 79 85 9 5 56 54 45 25 4 29 87 31 46 73 37 91 16 5 72 139 9 27 16 81 38 87 124 112 38 8 1 52 94 51 98 89 53 14 59 19 4 24 28 171 31 24 50 159 11 7 86 40...
output:
result:
Test #9:
score: 0
Time Limit Exceeded
input:
10000 10000 1102 1172 4429 4799 5086 6032 109 2039 1834 9108 4155 3616 174 5019 7709 6329 4145 8790 1759 3949 8600 7645 6860 3367 7497 8752 640 3960 5795 1546 113 7805 2919 9562 9125 6588 1573 5789 1910 2795 4075 4000 3189 556 4684 4901 4807 3198 8356 4081 3084 4862 8421 2023 886 1268 8826 2943 8476...
output:
result:
Test #10:
score: 0
Time Limit Exceeded
input:
10000 10000 4369 5585 4914 2369 2484 2516 1844 5275 6671 860 6424 3722 4807 1752 6554 9590 6670 2923 8872 246 3132 7199 8268 9182 8063 7339 3590 771 8154 9640 5410 8351 4824 3222 3552 7521 4652 7749 1867 7636 257 130 5087 1464 7618 6516 1193 9277 169 4584 9115 363 872 7247 2024 9845 4198 1794 1012 7...
output:
result:
Test #11:
score: 0
Time Limit Exceeded
input:
10000 10000 57 224 20 45 172 255 272 72 78 207 118 87 47 80 303 160 269 4 13 292 320 20 71 6 182 28 83 319 67 88 187 51 252 50 289 47 6 104 321 214 161 159 244 41 210 238 255 283 98 179 70 268 65 205 284 265 172 229 26 263 260 101 120 314 26 132 21 215 25 68 133 259 75 141 119 107 224 310 143 282 22...
output:
result:
Test #12:
score: 0
Time Limit Exceeded
input:
10000 10000 270 4 38 86 278 302 39 28 16 65 215 31 96 35 157 44 191 270 241 112 24 181 91 108 109 169 116 25 153 144 141 278 189 205 38 326 311 132 154 160 261 94 64 79 262 63 183 12 199 108 155 49 127 187 107 145 223 139 35 162 91 156 51 162 118 230 10 17 142 172 211 260 95 210 116 285 110 64 218 8...
output:
result:
Test #13:
score: 0
Time Limit Exceeded
input:
200000 200000 118934 195992 123246 58080 27980 167359 39421 127657 38819 119579 102077 66026 188968 45737 13734 253 13632 156052 64568 162976 91475 125529 7223 87592 16055 59515 114052 137901 103034 144187 74533 43665 115775 137180 180617 124276 60502 190661 23187 91058 193272 118804 68934 166092 12...
output:
result:
Test #14:
score: 0
Time Limit Exceeded
input:
200000 200000 5172 5838 4479 6536 311 6198 1477 3852 3083 4176 97 2086 2594 5940 226 51 4090 2516 5146 1888 5016 4570 71 1626 2158 4131 3194 59 5349 2106 2957 814 4271 5251 965 580 130 1515 3874 3713 5128 140 1719 924 53 2623 5400 1158 5047 6136 6205 2362 3816 2838 445 5123 75 2417 5683 520 5188 432...
output:
result:
Test #15:
score: 0
Time Limit Exceeded
input:
200000 200000 4888 2130 2294 5011 38 4442 16 1159 5694 2139 98 40 2676 2727 2123 4216 74 127 38 4918 38 3 3102 24 2798 4259 4340 480 3931 2604 4574 5428 1751 80 3186 2827 124 5145 4480 1177 3330 663 1933 114 2582 5143 5326 5736 5157 3862 3279 133 21 30 53 1056 5592 21 3018 18 22 148 5662 1489 2092 5...
output:
result:
Test #16:
score: 0
Time Limit Exceeded
input:
200000 200000 6498 67 96 221 108 879 5726 23 2534 2650 5059 3150 872 1546 6526 2074 5581 3200 6443 5207 1455 5216 5622 109 2157 3323 5783 56 3762 4116 25 74 6169 1 11 45 4501 6650 22 6586 42 4891 95 6504 6220 4358 3682 5051 21 3661 6512 6608 5006 46 97 6536 6522 4973 106 53 677 3784 38 2107 5601 284...
output:
result:
Test #17:
score: 0
Time Limit Exceeded
input:
1000000 1000000 339706 51482 773204 314921 652924 724747 962292 955667 453210 745585 322194 279895 298423 488877 4886 93270 781046 874791 832792 999157 525479 758883 715236 767662 793020 89963 700913 886570 133268 888616 872182 356703 389171 931968 797835 349103 280162 430912 211317 173487 935739 55...
output:
result:
Test #18:
score: 0
Time Limit Exceeded
input:
1000000 1000000 5924 66 11 21617 18383 33 22021 21252 32602 11762 102 15635 19155 17921 17781 6180 64 29027 100 12957 23796 24174 36 27445 9958 12 12778 31257 13873 31875 31854 6855 18736 28895 4727 8069 14914 13376 30634 11893 4316 9810 12613 19125 18712 10 25329 9579 4568 20807 15969 21444 61 2238...
output:
result:
Test #19:
score: 0
Time Limit Exceeded
input:
1000000 1000000 4911 31877 20155 18053 2309 19219 14047 3174 1572 31269 8791 9288 64 88 23830 27337 7798 18872 23785 3630 7060 4750 7156 32088 17 31362 23492 15773 22075 23416 10014 3325 2833 31381 4327 14864 28577 17304 25689 7151 6808 22066 14819 19879 8233 33255 5442 25475 5451 2195 20 10775 3151...
output:
result:
Test #20:
score: 0
Time Limit Exceeded
input:
1000000 1000000 31 3260 17263 6463 75 30801 25644 20232 3043 67 10738 26620 28625 67 80 20107 11724 24348 7433 107 29792 13556 9437 20077 17224 45 8185 17267 25824 11468 26965 18 7872 9303 10598 31721 22996 30434 50 31 25744 24630 10169 19626 21 8201 14023 5292 30171 29678 5157 26288 31056 2094 1593...