QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#139693#5405. 爬楼梯Lynkcat#0 276ms130448kbC++171.9kb2023-08-14 10:37:242024-07-04 01:41:46

Judging History

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

  • [2024-07-04 01:41:46]
  • 评测
  • 测评结果:0
  • 用时:276ms
  • 内存:130448kb
  • [2023-08-14 10:37:24]
  • 提交

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%