QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#139696#5405. 爬楼梯Lynkcat#0 410ms130960kbC++172.1kb2023-08-14 10:39:282024-07-04 01:41:46

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 01:41:46]
  • 评测
  • 测评结果:0
  • 用时:410ms
  • 内存:130960kb
  • [2023-08-14 10:39:28]
  • 提交

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%