QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#139698#5405. 爬楼梯Lynkcat#0 323ms131416kbC++172.1kb2023-08-14 10:41:542024-07-04 01:41:47

Judging History

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

  • [2024-07-04 01:41:47]
  • 评测
  • 测评结果:0
  • 用时:323ms
  • 内存:131416kb
  • [2023-08-14 10:41:54]
  • 提交

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%