QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#80108 | #5405. 爬楼梯 | tricyzhkx | 10 | 105ms | 16328kb | C++14 | 1.4kb | 2023-02-22 10:44:48 | 2023-02-22 10:44:51 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int rt[200010],h[200010],hh[200010],lc[4000010],rc[4000010],cnt[4000010],tot;
ll sum[4000010];
void update(int &rt,int l,int r,int x)
{
cnt[++tot]=cnt[rt];sum[tot]=sum[rt];lc[tot]=lc[rt];rc[tot]=rc[rt];rt=tot;
if(l==r) return cnt[rt]++,sum[rt]+=hh[l],void();
int mid=(l+r)/2;
if(x<=mid) update(lc[rt],l,mid,x);
else update(rc[rt],mid+1,r,x);
cnt[rt]=cnt[lc[rt]]+cnt[rc[rt]];
sum[rt]=sum[lc[rt]]+sum[rc[rt]];
}
ll query1(int r1,int r2,int l,int r,int x)
{
if(l==r) return x*hh[l];
int mid=(l+r)/2;
if(2*(cnt[lc[r2]]-cnt[lc[r1]])>=x) return query1(lc[r1],lc[r2],l,mid,x);
else return 2*(sum[lc[r2]]-sum[lc[r1]])+query1(rc[r1],rc[r2],mid+1,r,x-2*(cnt[lc[r2]]-cnt[lc[r1]]));
}
ll query2(int r1,int r2,int l,int r,int x)
{
if(l==r) return x*hh[l];
int mid=(l+r)/2;
if(2*(cnt[rc[r2]]-cnt[rc[r1]])>=x) return query2(rc[r1],rc[r2],mid+1,r,x);
else return 2*(sum[rc[r2]]-sum[rc[r1]])+query2(lc[r1],lc[r2],l,mid,x-2*(cnt[rc[r2]]-cnt[rc[r1]]));
}
int main()
{
int n,m,l,r;
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%d",&h[i]),hh[i]=h[i];
sort(hh+1,hh+n+1);
int len=unique(hh+1,hh+n+1)-hh-1;
for(int i=1;i<=n;i++) h[i]=lower_bound(hh+1,hh+len+1,h[i])-hh;
for(int i=1;i<=n;i++) update(rt[i]=rt[i-1],1,len,h[i]);
while(m--)
{
scanf("%d%d",&l,&r);
printf("%lld\n",query2(rt[l-1],rt[r],1,len,r-l)-query1(rt[l-1],rt[r],1,len,r-l));
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 5620kb
input:
10 10 323351358 540774025 513831404 171513818 162079008 234580967 887182642 765979034 329924749 677555871 2 4 1 6 8 10 2 5 1 9 4 6 9 10 2 10 1 8 8 10
output:
738520414 1530795597 872108570 1099707620 3632483908 145003918 347631122 3946786060 3442003862 872108570
result:
wrong answer 1st numbers differ - expected: '711577793', found: '738520414'
Subtask #2:
score: 10
Accepted
Test #11:
score: 10
Accepted
time: 84ms
memory: 14596kb
input:
200000 200000 1 2 1 2 1 1 1 2 2 1 1 1 1 1 1 1 1 2 1 1 1 1 2 1 2 1 1 1 1 1 2 2 1 1 1 1 1 1 2 2 2 1 1 2 2 1 2 1 2 1 2 1 1 1 1 1 1 2 1 1 2 1 1 1 1 2 1 2 1 2 2 1 1 2 1 1 1 2 1 1 2 1 2 1 1 1 2 1 2 2 2 2 1 2 2 1 1 2 2 1 2 2 1 1 1 1 2 2 2 1 1 1 1 1 2 2 1 1 1 1 2 1 2 1 2 2 2 2 1 1 2 1 2 1 1 2 1 2 2 2 1 1 1 ...
output:
17766 92870 56732 16462 79590 3872 79674 3370 151158 52672 41424 27644 52872 33690 47896 76136 59296 75972 113274 89092 114330 48490 24112 6810 164898 10914 9738 3316 33638 1510 16344 10722 89260 87924 12710 11498 464 61810 9336 100798 59812 170450 7374 78296 10230 173826 56696 106278 7504 141524 52...
result:
ok 200000 numbers
Test #12:
score: 0
Accepted
time: 97ms
memory: 13764kb
input:
200000 200000 1 1 1 2 2 1 1 1 2 1 1 2 1 1 2 2 1 1 2 1 1 2 2 2 1 1 2 2 2 1 1 1 1 2 2 2 1 1 2 1 2 1 1 2 1 1 1 2 1 2 2 2 1 1 1 1 1 1 1 1 1 1 2 2 2 1 2 1 1 2 1 2 1 1 2 2 2 1 1 2 1 2 2 1 1 2 2 1 1 1 1 2 1 1 1 1 2 2 2 1 2 2 2 1 2 1 1 2 1 2 2 2 1 1 1 2 2 2 2 2 2 1 1 2 1 1 2 1 2 2 2 1 1 1 2 2 2 2 1 2 2 2 2 ...
output:
34634 186070 40474 51812 74324 113772 143412 32850 159512 144058 50840 48476 63358 109344 61042 23484 20510 107934 83810 4928 35586 4418 115660 93302 74510 27160 118828 23978 63160 94808 93788 139628 116770 122686 6838 86990 129516 95050 127920 24436 125294 34376 92218 48038 18018 18998 30662 22800 ...
result:
ok 200000 numbers
Test #13:
score: 0
Accepted
time: 100ms
memory: 13800kb
input:
200000 200000 1 1 1 1 2 2 2 1 2 2 2 1 1 2 2 1 1 1 2 1 2 1 2 2 2 1 2 2 2 1 2 1 1 2 2 1 1 1 2 1 2 2 2 2 1 1 2 2 2 1 1 1 2 2 1 2 1 1 1 1 1 2 1 1 1 2 1 2 2 1 2 2 1 1 1 1 1 2 1 1 1 1 2 2 1 1 2 1 1 1 2 2 1 2 1 2 1 1 2 1 1 2 1 2 1 1 2 1 2 1 1 2 2 2 1 1 1 1 1 2 2 1 2 2 2 2 2 1 2 2 1 2 2 1 1 2 1 2 2 2 2 2 2 ...
output:
30180 3450 11204 13074 148502 130972 80042 52894 87820 109242 78962 28404 53748 7980 105422 56700 183670 14292 119848 143010 123090 85064 38840 47242 36332 14212 1644 36980 80758 111014 96414 96446 38670 8604 43886 88204 18960 87890 50892 107186 21344 1246 68720 63862 8724 52470 113760 12034 79240 1...
result:
ok 200000 numbers
Test #14:
score: 0
Accepted
time: 80ms
memory: 13732kb
input:
200000 200000 2 1 2 2 2 2 1 2 1 1 2 2 1 1 2 2 1 1 2 2 1 2 2 1 2 1 2 1 1 1 2 1 2 2 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 2 1 2 2 1 2 2 1 2 1 2 1 1 1 2 1 2 2 2 2 1 1 2 1 2 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 1 1 2 1 2 2 1 1 1 2 1 1 1 1 2 1 1 1 2 2 1 2 1 1 1 2 2 1 1 2 2 2 2 1 1 1 2 2 ...
output:
13022 134246 119602 92008 13162 73656 135398 88386 126060 9520 20108 115532 122146 49014 43682 25498 139232 18854 57476 127406 7926 51236 15566 108124 2018 55108 155408 13502 129392 137254 113628 34892 121138 150788 102334 34000 15094 26870 8520 96532 51126 52014 22954 66196 71570 96094 48444 42750 ...
result:
ok 200000 numbers
Test #15:
score: 0
Accepted
time: 105ms
memory: 13944kb
input:
200000 200000 1 1 1 1 1 1 1 2 2 2 1 2 1 1 1 1 2 1 1 2 2 1 2 2 2 1 1 1 1 2 1 1 1 1 2 2 2 2 2 2 1 2 2 2 2 1 1 1 2 1 1 1 1 2 2 1 1 2 2 1 2 2 2 2 1 1 2 1 2 2 1 2 1 2 2 1 2 2 1 2 1 2 2 1 2 1 2 1 2 2 2 2 1 2 1 2 1 1 1 2 1 1 1 2 1 2 1 1 1 2 1 1 2 2 1 2 2 2 2 1 1 1 1 1 1 2 1 2 2 2 2 1 1 1 1 2 2 2 1 1 1 2 1 ...
output:
48582 6872 24696 139252 76658 34278 35374 12294 122826 33 51450 149990 14150 79158 86212 146016 74428 52718 16548 169422 158372 96190 12256 24888 92880 87502 17934 61298 61614 65784 116924 33316 105728 31730 5162 6552 74088 10308 49304 48234 64130 48080 696 19114 81462 155474 101056 64116 32960 1650...
result:
ok 200000 numbers
Test #16:
score: 0
Accepted
time: 97ms
memory: 13912kb
input:
200000 200000 2 1 1 1 1 2 1 2 2 2 1 2 1 1 2 1 1 2 1 2 2 2 1 1 2 1 1 2 1 1 2 2 2 1 1 2 2 1 1 2 2 2 1 1 1 1 2 2 1 2 1 1 2 2 1 2 1 2 1 1 2 1 2 2 1 1 2 2 2 1 2 2 2 2 2 2 2 2 2 2 1 2 2 1 1 1 2 1 2 2 2 2 1 2 2 2 1 1 1 2 1 1 1 2 2 2 1 2 2 1 2 1 2 1 1 1 1 1 1 2 1 1 2 1 2 2 2 2 1 2 2 1 2 1 2 2 2 1 1 1 2 2 1 ...
output:
121730 5206 27378 36224 80674 95732 7556 37212 52848 78086 126638 39604 71342 28294 95564 136746 102870 4370 47068 38292 111382 74502 79350 33848 24888 55198 33708 79214 129152 125074 28038 128414 126114 24838 20918 5234 20476 85442 43684 125780 116178 7372 24176 14296 104564 33300 31370 107766 4671...
result:
ok 200000 numbers
Test #17:
score: 0
Accepted
time: 99ms
memory: 13944kb
input:
200000 200000 2 2 2 1 2 1 1 1 1 1 2 2 2 1 2 2 1 2 2 1 2 2 2 1 1 2 2 2 1 2 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 2 1 2 2 1 2 2 1 1 1 2 1 1 1 2 2 2 2 1 2 1 1 2 1 2 1 2 2 2 1 2 1 2 2 1 2 1 2 2 2 1 2 1 2 2 2 2 2 2 1 2 2 1 1 2 2 1 1 2 2 1 2 2 2 2 2 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 2 2 1 2 1 2 1 1 2 2 2 1 ...
output:
2208 102160 38506 104236 48716 141904 69076 94228 88968 14472 99250 85976 135724 41334 63612 61194 12336 72532 15200 182060 63002 91832 71954 67888 5262 33678 24420 27094 104114 146 328 150076 25408 64996 22704 95500 3398 89342 57594 3840 38392 73176 123976 36628 68980 88136 14884 30956 48840 85184 ...
result:
ok 200000 numbers
Test #18:
score: 0
Accepted
time: 94ms
memory: 13768kb
input:
200000 200000 2 1 2 1 1 2 2 1 2 1 2 2 2 1 2 1 2 1 1 1 1 1 2 1 1 2 2 1 1 1 2 2 2 2 1 2 1 2 1 1 2 1 1 2 1 1 2 2 1 1 2 2 2 2 1 1 2 1 1 1 1 1 2 2 2 2 1 1 2 1 1 1 2 2 2 2 1 2 1 1 1 1 2 1 1 2 1 2 1 2 2 1 1 2 1 1 1 1 1 1 2 2 1 2 1 1 1 1 1 1 2 1 2 1 1 1 2 1 1 1 2 2 2 2 1 2 2 1 2 1 2 1 2 1 1 1 2 1 1 1 1 1 1 ...
output:
40110 86054 7820 111738 7270 61898 35328 8392 25652 15106 90212 48114 40102 42102 93144 122112 5888 25884 19168 33284 25020 137562 66590 16468 7898 44420 33858 108998 17768 31096 9342 78576 40496 60600 107784 105508 39370 73000 151258 47718 61834 116814 88044 116160 55036 167796 135812 90236 69586 9...
result:
ok 200000 numbers
Test #19:
score: 0
Accepted
time: 83ms
memory: 13712kb
input:
200000 200000 2 2 1 2 1 2 2 2 1 1 2 1 1 1 1 1 2 1 2 2 1 1 2 1 2 2 2 2 2 1 2 2 1 2 2 1 2 1 2 2 2 1 1 1 2 1 2 1 1 1 2 1 1 1 2 2 1 2 1 1 1 1 1 1 2 2 2 1 1 1 2 2 1 1 1 2 2 1 2 1 2 1 2 2 2 1 1 2 1 2 1 1 2 1 1 2 2 1 2 2 2 1 2 2 1 2 2 2 2 1 1 1 2 2 1 1 2 1 1 2 1 1 2 2 1 2 2 2 1 1 2 1 1 1 1 1 2 2 2 2 2 2 2 ...
output:
162036 18978 42904 66578 155524 15368 54002 86214 94220 110102 88156 98612 2446 115006 99172 32232 62964 57398 114400 81306 35150 119398 71542 38160 43048 32222 60084 32398 22606 130652 154536 73254 29208 65734 49880 19994 26114 63156 17292 51504 16392 108188 173554 28578 60564 14456 74482 144720 49...
result:
ok 200000 numbers
Test #20:
score: 0
Accepted
time: 76ms
memory: 13704kb
input:
200000 200000 1 1 2 1 1 1 2 2 1 1 2 2 1 1 2 2 2 2 1 1 1 2 2 2 1 1 2 2 2 2 2 2 1 2 1 2 1 2 1 1 1 1 1 1 1 2 2 1 2 1 1 1 1 1 2 2 2 2 2 1 1 2 2 2 2 1 1 1 2 1 2 2 2 1 1 2 2 2 2 2 1 1 2 2 2 1 1 1 1 1 1 2 2 1 2 1 1 2 2 1 2 2 2 2 2 1 2 1 1 2 2 1 2 2 2 2 1 1 2 2 2 1 1 2 2 2 1 1 1 1 2 1 2 1 2 1 2 1 2 2 1 1 2 ...
output:
23836 30092 180998 59448 117750 56030 90790 36820 134968 97314 100600 70630 69220 86388 87458 36282 92862 36224 35728 52382 82620 85024 6276 73508 41444 61282 103070 141644 91920 16652 15544 70666 136362 37674 56476 20866 138534 120686 87134 81934 121702 94000 15266 153606 116372 114098 13844 113104...
result:
ok 200000 numbers
Subtask #3:
score: 0
Wrong Answer
Dependency #2:
100%
Accepted
Test #21:
score: 0
Wrong Answer
time: 94ms
memory: 16328kb
input:
200000 200000 2 2 1 3 3 1 1 3 1 2 3 1 1 2 1 2 2 3 3 1 2 3 1 3 1 1 2 1 3 1 2 1 3 2 3 2 3 2 2 3 2 3 1 1 1 2 3 2 1 1 1 2 2 2 1 1 3 2 3 1 2 1 2 2 3 1 3 2 2 1 2 3 1 2 2 1 1 2 1 1 2 2 1 2 2 2 3 1 1 3 2 3 1 2 2 1 2 3 1 2 3 2 3 3 1 2 1 1 1 1 2 1 1 2 1 3 2 1 2 3 1 1 2 2 2 3 2 2 2 1 2 1 2 2 3 3 3 2 2 3 1 3 1 ...
output:
67298 55468 159392 3114 154332 73750 83244 197408 3814 64544 45538 222396 73420 101340 121448 49368 122248 95026 5206 51198 53084 64706 74262 14474 3538 209226 26128 27000 80008 37380 32102 65130 4836 16024 104892 53806 66150 1910 60680 36392 169856 12842 68530 13216 50144 57006 91856 95944 21622 16...
result:
wrong answer 181408th numbers differ - expected: '3', found: '4'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%