QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#139693 | #5405. 爬楼梯 | Lynkcat# | 0 | 276ms | 130448kb | C++17 | 1.9kb | 2023-08-14 10:37:24 | 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);
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: 7756kb
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:
396202828 1458293638 524477448 1090272810 3306227236 135569108 347631122 3252716078 3280731512 524477448
result:
wrong answer 1st numbers differ - expected: '711577793', found: '396202828'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 276ms
memory: 130448kb
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:
17764 92869 56731 16461 79589 3872 79673 3368 151157 52670 41423 27643 52870 33688 47894 76135 59295 75970 113273 89091 114329 48488 24111 6810 164896 10914 9737 3316 33637 1508 16343 10722 89259 87923 12708 11498 463 61809 9334 100796 59811 170448 7372 78295 10228 173824 56695 106276 7502 141523 52...
result:
wrong answer 1st numbers differ - expected: '17766', found: '17764'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%