UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#211093#2407. 双端队列FHL272695ms1856kbC++111.0kb2024-08-09 11:20:002024-08-09 12:46:34

answer

#include <deque>
#include <iostream>
#define int long long
using namespace std;
unsigned int T;
deque<int> deq;
signed main() {
  	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
  	cin >> T;
  	while (T -- ) {
  		int op, x, k, c;
    	cin >> op;
    	if (op == 1) {
      		cin >> x;
      		deq.push_front(x);
    	}
		else if (op == 2) {
      		cin >> x;
      		deq.push_back(x);
    	}
		else if (op == 3) deq.pop_front();
    	else if (op == 4) deq.pop_back();
    	else if (op == 5) {
      		cin >> k >> c;
      		unsigned int cnt = 0;
      		int sum = 0;
      		for (auto i = deq.begin(); i < deq.end() && cnt < c; i += k) {
        		++ cnt;
        		sum += *i;
      		}
      		cout << sum << "\n";
    	}
		else {
      		cin >> k >> c;
      		unsigned int cnt = 0;
      		int sum = 0;
      		for (auto i = deq.rbegin(); i < deq.rend() && cnt < c; i += k) {
        		++ cnt;
        		sum += *i;
      		}
      		cout << sum << "\n";
    	}
  	}
  	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 11
Accepted

Test #1:

score: 11
Accepted
time: 0ms
memory: 1276kb

input:

3000
2 -219498
2 -293012
2 340429
2 282883
2 17839
2 300008
2 -275152
2 -328138
2 337993
2 -149230
2...

output:

-529420
308873
-346656
-375516
-378742
243014
-2505874
907290
84617
-501772
-1601553
-1056004
112539...

result:

ok 213 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 1272kb

input:

3000
6 8 1
2 58786
2 -84977
2 129564
2 -330887
2 -311982
2 -7146
2 -148740
2 -300250
2 232985
2 3179...

output:

0
-282257
58786
-19835
329884
-152358
1681839
-460403
104320
776811
801627
60401
230071
88464
-19985...

result:

ok 228 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 1264kb

input:

3000
1 215822
1 171040
1 226169
1 26739
4
1 185368
1 -10112
1 -1737
1 130697
1 68004
1 43591
4
5 5 3...

output:

228959
187082
-91148
-439993
261733
-100318
175284
517015
236030
284075
403830
-72339
324233
578959
...

result:

ok 220 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 1264kb

input:

3000
1 -307707
5 8 1
1 -304370
1 -219623
1 -134160
1 -132201
4
4
1 -41278
1 44317
1 -165751
4
1 3336...

output:

-307707
81937
34424
183227
94915
-128971
-145023
-196547
-21813
257186
294135
1233309
-243701
88394
...

result:

ok 190 lines

Test #5:

score: 0
Accepted
time: 1ms
memory: 1264kb

input:

3000
2 129888
2 -37535
2 -263788
2 -201324
2 -253116
2 -66187
2 -332613
6 15 1
2 314953
2 -29219
3
2...

output:

-332613
-201324
-81278
314953
-205703
194751
-296765
159811
-452389
337751
173086
373732
141101
1178...

result:

ok 217 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 1264kb

input:

3000
2 276577
2 317056
2 -124108
3
2 -327284
2 -72611
3
2 129759
2 68809
2 348432
2 152042
2 -266989...

output:

-643554
-327284
-525557
245608
-296073
-317425
150207
118939
-77907
-250488
93061
86951
350411
-2897...

result:

ok 200 lines

Subtask #2:

score: 16
Accepted

Test #7:

score: 16
Accepted
time: 0ms
memory: 1276kb

input:

3000
2 -219498
2 -293012
2 340429
2 282883
2 17839
2 300008
2 -275152
2 -328138
2 337993
2 -149230
2...

output:

-529420
308873
-346656
-375516
-378742
243014
-2505874
907290
84617
-501772
-1601553
-1056004
112539...

result:

ok 213 lines

Test #8:

score: 0
Accepted
time: 0ms
memory: 1276kb

input:

3000
6 8 1
2 58786
2 -84977
2 129564
2 -330887
2 -311982
2 -7146
2 -148740
2 -300250
2 232985
2 3179...

output:

0
-282257
58786
-19835
329884
-152358
1681839
-460403
104320
776811
801627
60401
230071
88464
-19985...

result:

ok 228 lines

Test #9:

score: 0
Accepted
time: 0ms
memory: 1264kb

input:

3000
1 215822
1 171040
1 226169
1 26739
4
1 185368
1 -10112
1 -1737
1 130697
1 68004
1 43591
4
5 5 3...

output:

228959
187082
-91148
-439993
261733
-100318
175284
517015
236030
284075
403830
-72339
324233
578959
...

result:

ok 220 lines

Test #10:

score: 0
Accepted
time: 0ms
memory: 1268kb

input:

3000
1 -307707
5 8 1
1 -304370
1 -219623
1 -134160
1 -132201
4
4
1 -41278
1 44317
1 -165751
4
1 3336...

output:

-307707
81937
34424
183227
94915
-128971
-145023
-196547
-21813
257186
294135
1233309
-243701
88394
...

result:

ok 190 lines

Test #11:

score: 0
Accepted
time: 0ms
memory: 1264kb

input:

3000
2 129888
2 -37535
2 -263788
2 -201324
2 -253116
2 -66187
2 -332613
6 15 1
2 314953
2 -29219
3
2...

output:

-332613
-201324
-81278
314953
-205703
194751
-296765
159811
-452389
337751
173086
373732
141101
1178...

result:

ok 217 lines

Test #12:

score: 0
Accepted
time: 0ms
memory: 1268kb

input:

3000
2 276577
2 317056
2 -124108
3
2 -327284
2 -72611
3
2 129759
2 68809
2 348432
2 152042
2 -266989...

output:

-643554
-327284
-525557
245608
-296073
-317425
150207
118939
-77907
-250488
93061
86951
350411
-2897...

result:

ok 200 lines

Test #13:

score: 0
Accepted
time: 533ms
memory: 1856kb

input:

351493
2 30700
2 97140
2 192604
2 -23754
2 271281
2 -253753
2 260860
2 63425
2 -301042
2 192887
2 25...

output:

-132828
137348
-11294
258928
1317204
209910
-441868
-147700
-364841
368483
347448
657793
1244669
186...

result:

ok 23157 lines

Test #14:

score: 0
Accepted
time: 541ms
memory: 1856kb

input:

351493
2 -141259
2 -319586
2 -298337
2 212471
2 203230
2 -195525
2 -174121
2 -146721
2 -269066
2 -95...

output:

-227773
-141259
-90087
18273
-563675
-223765
-482019
-293685
-332381
-864545
-546890
1352463
511539
...

result:

ok 23551 lines

Test #15:

score: 0
Accepted
time: 55ms
memory: 1296kb

input:

351493
1 -166224
1 141673
1 -59557
1 16602
1 -202211
1 -41204
1 328426
1 8503
1 -293263
1 -157672
1 ...

output:

21132
-80252
-101734
203582
260488
-122876
153114
415131
511155
811888
-366466
622775
472740
-39971
...

result:

ok 23175 lines

Test #16:

score: 0
Accepted
time: 54ms
memory: 1296kb

input:

351493
1 -128250
5 2 1
1 -131922
1 -76441
1 115257
1 306636
1 -240558
1 81818
1 268991
1 17051
1 607...

output:

-128250
-138737
-279670
132377
-1166970
-442744
-859519
-3685480
-440229
-1698481
-106164
-241278
-1...

result:

ok 23524 lines

Test #17:

score: 0
Accepted
time: 54ms
memory: 1296kb

input:

351493
5 12 1
2 -34134
2 153473
2 -178692
2 -137286
2 150203
2 337403
2 115110
2 -184140
2 -182598
2...

output:

0
-34134
-66529
-333706
969811
141056
1284434
-650732
-914938
-800123
807448
-1231374
-16475
-114646...

result:

ok 23402 lines

Test #18:

score: 0
Accepted
time: 55ms
memory: 1300kb

input:

351493
2 -214184
2 -31341
2 48340
2 -271735
2 -100493
5 1 5
2 -231581
2 221193
2 -11430
2 -7875
2 27...

output:

-569413
-569514
-297779
-569413
-264726
-436730
-949743
-430251
-477907
-544048
-444607
259748
-1101...

result:

ok 23402 lines

Subtask #3:

score: 0
Time Limit Exceeded

Test #19:

score: 0
Time Limit Exceeded

input:

3000000
1 109596
1 18831
2 89913
1 -164180
2 -256425
2 179608
2 -41750
1 245023
1 185637
1 79804
2 -...

output:

474711
-346102
128379
-193118
-93743
-265084
313689
-18092
-94553
892922
28562
96170
-454664
-270538...

result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #24:

score: 0
Time Limit Exceeded

input:

3000000
1 109596
1 18831
2 89913
1 -164180
2 -256425
2 179608
2 -41750
1 245023
1 185637
1 79804
2 -...

output:

474711
-346102
128379
-193118
-93743
-265084
313689
-18092
-94553
892922
28562
96170
-454664
-270538...

result:


Subtask #5:

score: 0
Time Limit Exceeded

Test #34:

score: 31
Accepted
time: 0ms
memory: 1272kb

input:

3000
2 -219498
2 -293012
2 340429
2 282883
2 17839
2 300008
2 -275152
2 -328138
2 337993
2 -149230
2...

output:

-529420
308873
-346656
-375516
-378742
243014
-2505874
907290
84617
-501772
-1601553
-1056004
112539...

result:

ok 213 lines

Test #35:

score: 0
Accepted
time: 1ms
memory: 1272kb

input:

3000
6 8 1
2 58786
2 -84977
2 129564
2 -330887
2 -311982
2 -7146
2 -148740
2 -300250
2 232985
2 3179...

output:

0
-282257
58786
-19835
329884
-152358
1681839
-460403
104320
776811
801627
60401
230071
88464
-19985...

result:

ok 228 lines

Test #36:

score: 0
Accepted
time: 0ms
memory: 1268kb

input:

3000
1 215822
1 171040
1 226169
1 26739
4
1 185368
1 -10112
1 -1737
1 130697
1 68004
1 43591
4
5 5 3...

output:

228959
187082
-91148
-439993
261733
-100318
175284
517015
236030
284075
403830
-72339
324233
578959
...

result:

ok 220 lines

Test #37:

score: 0
Accepted
time: 0ms
memory: 1268kb

input:

3000
1 -307707
5 8 1
1 -304370
1 -219623
1 -134160
1 -132201
4
4
1 -41278
1 44317
1 -165751
4
1 3336...

output:

-307707
81937
34424
183227
94915
-128971
-145023
-196547
-21813
257186
294135
1233309
-243701
88394
...

result:

ok 190 lines

Test #38:

score: 0
Accepted
time: 0ms
memory: 1268kb

input:

3000
2 129888
2 -37535
2 -263788
2 -201324
2 -253116
2 -66187
2 -332613
6 15 1
2 314953
2 -29219
3
2...

output:

-332613
-201324
-81278
314953
-205703
194751
-296765
159811
-452389
337751
173086
373732
141101
1178...

result:

ok 217 lines

Test #39:

score: 0
Accepted
time: 0ms
memory: 1268kb

input:

3000
2 276577
2 317056
2 -124108
3
2 -327284
2 -72611
3
2 129759
2 68809
2 348432
2 152042
2 -266989...

output:

-643554
-327284
-525557
245608
-296073
-317425
150207
118939
-77907
-250488
93061
86951
350411
-2897...

result:

ok 200 lines

Test #40:

score: 0
Accepted
time: 563ms
memory: 1852kb

input:

351493
2 30700
2 97140
2 192604
2 -23754
2 271281
2 -253753
2 260860
2 63425
2 -301042
2 192887
2 25...

output:

-132828
137348
-11294
258928
1317204
209910
-441868
-147700
-364841
368483
347448
657793
1244669
186...

result:

ok 23157 lines

Test #41:

score: 0
Accepted
time: 551ms
memory: 1856kb

input:

351493
2 -141259
2 -319586
2 -298337
2 212471
2 203230
2 -195525
2 -174121
2 -146721
2 -269066
2 -95...

output:

-227773
-141259
-90087
18273
-563675
-223765
-482019
-293685
-332381
-864545
-546890
1352463
511539
...

result:

ok 23551 lines

Test #42:

score: 0
Accepted
time: 91ms
memory: 1296kb

input:

351493
1 -166224
1 141673
1 -59557
1 16602
1 -202211
1 -41204
1 328426
1 8503
1 -293263
1 -157672
1 ...

output:

21132
-80252
-101734
203582
260488
-122876
153114
415131
511155
811888
-366466
622775
472740
-39971
...

result:

ok 23175 lines

Test #43:

score: 0
Accepted
time: 94ms
memory: 1300kb

input:

351493
1 -128250
5 2 1
1 -131922
1 -76441
1 115257
1 306636
1 -240558
1 81818
1 268991
1 17051
1 607...

output:

-128250
-138737
-279670
132377
-1166970
-442744
-859519
-3685480
-440229
-1698481
-106164
-241278
-1...

result:

ok 23524 lines

Test #44:

score: 0
Accepted
time: 54ms
memory: 1300kb

input:

351493
5 12 1
2 -34134
2 153473
2 -178692
2 -137286
2 150203
2 337403
2 115110
2 -184140
2 -182598
2...

output:

0
-34134
-66529
-333706
969811
141056
1284434
-650732
-914938
-800123
807448
-1231374
-16475
-114646...

result:

ok 23402 lines

Test #45:

score: 0
Accepted
time: 48ms
memory: 1296kb

input:

351493
2 -214184
2 -31341
2 48340
2 -271735
2 -100493
5 1 5
2 -231581
2 221193
2 -11430
2 -7875
2 27...

output:

-569413
-569514
-297779
-569413
-264726
-436730
-949743
-430251
-477907
-544048
-444607
259748
-1101...

result:

ok 23402 lines

Test #46:

score: -31
Time Limit Exceeded

input:

3000000
1 109596
1 18831
2 89913
1 -164180
2 -256425
2 179608
2 -41750
1 245023
1 185637
1 79804
2 -...

output:

474711
-346102
128379
-193118
-93743
-265084
313689
-18092
-94553
892922
28562
96170
-454664
-270538...

result: