QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#80108#5405. 爬楼梯tricyzhkx10 105ms16328kbC++141.4kb2023-02-22 10:44:482023-02-22 10:44:51

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-22 10:44:51]
  • 评测
  • 测评结果:10
  • 用时:105ms
  • 内存:16328kb
  • [2023-02-22 10:44:48]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int rt[200010],h[200010],hh[200010],lc[4000010],rc[4000010],cnt[4000010],tot;
ll sum[4000010];
void update(int &rt,int l,int r,int x)
{
	cnt[++tot]=cnt[rt];sum[tot]=sum[rt];lc[tot]=lc[rt];rc[tot]=rc[rt];rt=tot;
	if(l==r) return cnt[rt]++,sum[rt]+=hh[l],void();
	int mid=(l+r)/2;
	if(x<=mid) update(lc[rt],l,mid,x);
	else update(rc[rt],mid+1,r,x);
	cnt[rt]=cnt[lc[rt]]+cnt[rc[rt]];
	sum[rt]=sum[lc[rt]]+sum[rc[rt]];
}
ll query1(int r1,int r2,int l,int r,int x)
{
	if(l==r) return x*hh[l];
	int mid=(l+r)/2;
	if(2*(cnt[lc[r2]]-cnt[lc[r1]])>=x) return query1(lc[r1],lc[r2],l,mid,x);
	else return 2*(sum[lc[r2]]-sum[lc[r1]])+query1(rc[r1],rc[r2],mid+1,r,x-2*(cnt[lc[r2]]-cnt[lc[r1]]));
}
ll query2(int r1,int r2,int l,int r,int x)
{
	if(l==r) return x*hh[l];
	int mid=(l+r)/2;
	if(2*(cnt[rc[r2]]-cnt[rc[r1]])>=x) return query2(rc[r1],rc[r2],mid+1,r,x);
	else return 2*(sum[rc[r2]]-sum[rc[r1]])+query2(lc[r1],lc[r2],l,mid,x-2*(cnt[rc[r2]]-cnt[rc[r1]]));
}
int main()
{
	int n,m,l,r;
	cin>>n>>m;
	for(int i=1;i<=n;i++) scanf("%d",&h[i]),hh[i]=h[i];
	sort(hh+1,hh+n+1);
	int len=unique(hh+1,hh+n+1)-hh-1;
	for(int i=1;i<=n;i++) h[i]=lower_bound(hh+1,hh+len+1,h[i])-hh;
	for(int i=1;i<=n;i++) update(rt[i]=rt[i-1],1,len,h[i]);
	while(m--)
	{
		scanf("%d%d",&l,&r);
		printf("%lld\n",query2(rt[l-1],rt[r],1,len,r-l)-query1(rt[l-1],rt[r],1,len,r-l));
	}
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 5620kb

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:

738520414
1530795597
872108570
1099707620
3632483908
145003918
347631122
3946786060
3442003862
872108570

result:

wrong answer 1st numbers differ - expected: '711577793', found: '738520414'

Subtask #2:

score: 10
Accepted

Test #11:

score: 10
Accepted
time: 84ms
memory: 14596kb

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: 97ms
memory: 13764kb

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: 100ms
memory: 13800kb

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: 80ms
memory: 13732kb

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: 105ms
memory: 13944kb

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: 97ms
memory: 13912kb

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: 99ms
memory: 13944kb

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: 94ms
memory: 13768kb

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: 83ms
memory: 13712kb

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: 0
Accepted
time: 76ms
memory: 13704kb

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:

23836
30092
180998
59448
117750
56030
90790
36820
134968
97314
100600
70630
69220
86388
87458
36282
92862
36224
35728
52382
82620
85024
6276
73508
41444
61282
103070
141644
91920
16652
15544
70666
136362
37674
56476
20866
138534
120686
87134
81934
121702
94000
15266
153606
116372
114098
13844
113104...

result:

ok 200000 numbers

Subtask #3:

score: 0
Wrong Answer

Dependency #2:

100%
Accepted

Test #21:

score: 0
Wrong Answer
time: 94ms
memory: 16328kb

input:

200000 200000
2 2 1 3 3 1 1 3 1 2 3 1 1 2 1 2 2 3 3 1 2 3 1 3 1 1 2 1 3 1 2 1 3 2 3 2 3 2 2 3 2 3 1 1 1 2 3 2 1 1 1 2 2 2 1 1 3 2 3 1 2 1 2 2 3 1 3 2 2 1 2 3 1 2 2 1 1 2 1 1 2 2 1 2 2 2 3 1 1 3 2 3 1 2 2 1 2 3 1 2 3 2 3 3 1 2 1 1 1 1 2 1 1 2 1 3 2 1 2 3 1 1 2 2 2 3 2 2 2 1 2 1 2 2 3 3 3 2 2 3 1 3 1 ...

output:

67298
55468
159392
3114
154332
73750
83244
197408
3814
64544
45538
222396
73420
101340
121448
49368
122248
95026
5206
51198
53084
64706
74262
14474
3538
209226
26128
27000
80008
37380
32102
65130
4836
16024
104892
53806
66150
1910
60680
36392
169856
12842
68530
13216
50144
57006
91856
95944
21622
16...

result:

wrong answer 181408th numbers differ - expected: '3', found: '4'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%