QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#139698 | #5405. 爬楼梯 | Lynkcat# | 0 | 323ms | 131416kb | C++17 | 2.1kb | 2023-08-14 10:41:54 | 2024-07-04 01:41:47 |
Judging History
answer
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) (int)((x).size())
#define int ll
#define N 200005
using namespace std;
int tr[N*32],lson[N*32],rson[N*32],sm[N*32];
int cnt;
int a[N],b[N],p[N],n,q,rt[N];
void update(int &k,int lst,int l,int r,int L,int x)
{
k=++cnt;
sm[k]=sm[lst];
tr[k]=tr[lst];
lson[k]=lson[lst];
rson[k]=rson[lst];
tr[k]++;
sm[k]+=x;
if (l==r) return;
int mid=l+(r-l)/2;
if (L<=mid) update(lson[k],lson[lst],l,mid,L,x);
else update(rson[k],rson[lst],mid+1,r,L,x);
}
int qry(int k,int lst,int l,int r,int x)
{
// cout<<k<<" "<<endl;
if (x==0) return 0;
if (l==r)
{
return sm[k]-sm[lst];
}
int mid=l+(r-l)/2;
if (tr[rson[k]]-tr[rson[lst]]<x)
{
x-=tr[rson[k]]-tr[rson[lst]];
return qry(lson[k],lson[lst],l,mid,x)+sm[rson[k]]-sm[rson[lst]];
}
return qry(rson[k],rson[lst],mid+1,r,x);
}
void BellaKira()
{
cin>>n>>q;
for (int i=1;i<=n;i++)
cin>>a[i],p[i]=i;
sort(p+1,p+n+1,[&](int x,int y)
{
return a[x]<a[y];
});
for (int i=1;i<=n;i++) b[p[i]]=i;
for (int i=1;i<=n;i++)
{
update(rt[i],rt[i-1],1,n,b[i],a[i]);
}
while (q--)
{
int l,r;
cin>>l>>r;
if ((r-l+1)&1)
{
int tot=(r-l+1)/2;
int ans=qry(rt[r],rt[l-1],1,n,tot)*4-
1*qry(rt[r],rt[l-1],1,n,tot+tot-1)
-qry(rt[r],rt[l-1],1,n,tot+tot+1);
ans=max(ans,qry(rt[r],rt[l-1],1,n,tot+1)*2-
2*(qry(rt[r],rt[l-1],1,n,tot+tot+1)-qry(rt[r],rt[l-1],1,n,tot+1))
-(qry(rt[r],rt[l-1],1,n,tot+1)-qry(rt[r],rt[l-1],1,n,tot-1)));
cout<<ans<<'\n';
} else
{
int tot=(r-l+1)/2;
int ans=qry(rt[r],rt[l-1],1,n,tot)*4-
2*qry(rt[r],rt[l-1],1,n,tot+tot)
-(qry(rt[r],rt[l-1],1,n,tot)-qry(rt[r],rt[l-1],1,n,tot-1))
+(qry(rt[r],rt[l-1],1,n,tot+1)-qry(rt[r],rt[l-1],1,n,tot));
cout<<ans<<'\n';
}
}
}
signed main()
{
IOS;
cin.tie(0);
int T=1;
while (T--)
{
BellaKira();
}
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 7696kb
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:
711577793 1530795597 783685407 1099707620 3448577253 135569108 347631122 3919843439 3442003862 783685407
result:
wrong answer 5th numbers differ - expected: '3625910517', found: '3448577253'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 10
Accepted
time: 316ms
memory: 130016kb
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: 284ms
memory: 131088kb
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: 285ms
memory: 130068kb
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: 289ms
memory: 130164kb
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: 295ms
memory: 130600kb
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: 295ms
memory: 131416kb
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: 299ms
memory: 129244kb
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: 284ms
memory: 130664kb
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: 312ms
memory: 129884kb
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: -10
Wrong Answer
time: 323ms
memory: 131208kb
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:
result:
wrong output format Output file not found: ""
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%