QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#139696 | #5405. 爬楼梯 | Lynkcat# | 0 | 410ms | 130960kb | C++17 | 2.1kb | 2023-08-14 10:39:28 | 2024-07-04 01:41:46 |
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)
{
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+tot)-qry(rt[r],rt[l-1],1,n,tot+tot-1));
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: 0ms
memory: 7740kb
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 1458293638 783685407 1090272810 3448577253 135569108 347631122 3919843439 3280731512 783685407
result:
wrong answer 2nd numbers differ - expected: '1530795597', found: '1458293638'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 410ms
memory: 130960kb
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:
wrong answer 28065th numbers differ - expected: '36592', found: '109031'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%