QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#537720#5258. MortgageUESTC_DECAYALIWA 326ms42384kbC++202.0kb2024-08-30 17:44:322024-08-30 17:44:33

Judging History

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

  • [2024-08-30 17:44:33]
  • 评测
  • 测评结果:WA
  • 用时:326ms
  • 内存:42384kb
  • [2024-08-30 17:44:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N = 2e5+5;
int n, m, A[N], sum[N];
struct Node{
    int R, id;
    bool operator<(const Node &b)const{return R!=b.R ? R>b.R : id<b.id;}
};
vector<Node> qry[N];
int ans[N];

struct Convh{
    vector<int> stk; int sz=0;

    void add(int id){
        while (sz>1 &&
            (sum[stk[sz-1]]-sum[id])*(stk[sz-2]-stk[sz-1]) >
            (sum[stk[sz-2]]-sum[stk[sz-1]])*(stk[sz-1]-id))
            stk.pop_back(), --sz;
        stk.push_back(id); ++sz;
    } 

    int find(int id){
        int L=0, R=sz-1;
        while (R - L > 20){
            int M1 = L+(R-L)/2, M2 = M1+1;
            int res1 = (sum[stk[M1]]-sum[id])*(stk[M2]-id);
            int res2 = (sum[stk[M2]]-sum[id])*(stk[M1]-id);
            if (res1 == res2) L=R;
            else if (res1 < res2) R = M2;
            else L = M1;
            // std::cerr << "FUCK\n";
        }
        int ans = 0x7f7f7f7f;
        while(L <= R) ans = min(ans, (sum[stk[L]]-sum[id])/(stk[L]-id)), L++;
        if (ans>=0) return ans;
        else return -1;
    }
};

Convh c[N];

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i=1; i<=n; ++i) cin >> A[i], sum[i] = sum[i-1]+A[i];
    for (int i=1; i<=m; ++i){
        int s, k; cin >> s >> k;
        qry[s-1].push_back(Node{s+k-1, i});
    }

    for (int i=0; i<n; ++i) sort(qry[i].begin(), qry[i].end());

    for (int i=n; i>=0; --i){
        for(auto [q, id]: qry[i]) {
            int l = i + 1, r = q + 1, a = 0x7f7f7f7f;
            for(int j = r; j; j -= j&-j) if(c[j].sz) a = std::min(a, c[j].find(l - 1));// std::cerr << "FUCK\n";
            ans[id] = a;
        }
        for(int j = i + 1; j <= n + 1; j += j&-j) c[j].add(i);// std::cerr << "Blyat\n";
    }

    for(int i = 1; i <= m; ++i) {
        if(ans[i] < 0) std::cout << "stay with parents\n";
        else           std::cout << ans[i] << char(10);
    }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 5680kb

input:

10 10
21 18 19 18 16 15 13 13 13 10
10 1
6 4
7 3
2 2
6 5
2 6
3 2
4 1
1 5
6 3

output:

10
13
13
18
12
16
18
18
18
13

result:

ok 10 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 5744kb

input:

1000 1000
196 207 195 207 200 203 202 204 205 191 190 188 203 198 201 188 203 198 196 196 200 195 200 206 193 198 186 196 200 185 202 195 203 199 185 199 202 191 184 194 195 194 193 195 184 197 189 193 186 187 193 193 196 186 195 193 186 192 188 188 187 197 179 188 195 196 197 186 194 183 189 185 19...

output:

158
16
110
64
160
118
169
63
172
128
93
82
118
119
86
32
174
145
139
84
149
120
133
155
108
110
65
178
90
99
118
91
133
85
151
76
130
50
91
99
95
78
110
87
119
141
68
81
172
82
112
139
136
81
79
16
51
31
104
116
108
38
75
176
156
55
165
112
146
74
68
172
112
157
94
177
111
166
110
112
98
155
109
155...

result:

ok 1000 lines

Test #3:

score: 0
Accepted
time: 2ms
memory: 7864kb

input:

1000 1000
1023 912 1076 907 1015 1078 1075 1031 930 925 925 960 1013 893 1052 920 967 1046 960 1077 888 883 1045 1049 1034 1062 967 1021 986 938 871 916 901 1032 1003 1020 900 909 920 1048 884 859 1016 922 945 955 1002 1033 947 1025 970 862 929 908 912 956 873 845 933 873 921 918 904 884 1033 900 99...

output:

220
651
401
454
516
692
597
294
779
418
468
679
293
348
920
172
554
303
282
104
580
824
569
376
221
226
454
232
794
469
788
925
394
308
245
624
614
422
252
407
149
529
178
612
584
429
629
357
477
886
896
517
114
762
560
546
516
735
275
818
304
608
214
685
205
561
470
826
844
335
618
327
651
799
843
...

result:

ok 1000 lines

Test #4:

score: 0
Accepted
time: 2ms
memory: 7816kb

input:

1000 1000
938 360 206 545 664 694 717 653 217 681 574 932 125 191 677 87 875 177 253 29 748 915 222 288 771 785 233 112 922 847 473 267 365 610 76 404 776 3 821 971 730 988 652 263 525 233 91 821 319 876 467 617 271 899 53 650 874 369 746 307 592 915 309 93 387 885 800 387 617 382 928 963 540 943 22...

output:

335
9
125
426
415
352
362
292
456
475
399
477
341
387
500
475
201
483
246
509
280
496
407
433
470
445
340
459
472
439
472
411
458
327
227
428
207
363
77
267
231
204
333
387
137
315
23
33
471
313
37
202
31
177
425
125
403
177
371
480
329
468
163
340
416
458
202
202
143
345
478
17
383
375
493
213
382
...

result:

ok 1000 lines

Test #5:

score: 0
Accepted
time: 2ms
memory: 5764kb

input:

1000 1000
45 -80 65 -47 -17 75 49 79 38 65 25 64 53 74 0 -43 38 22 -48 -6 37 12 24 -36 -9 9 -64 -66 -31 91 -5 29 62 98 56 133 64 59 93 -6 97 89 7 121 125 21 39 95 131 60 -33 -4 6 63 52 44 25 -38 24 -40 94 135 129 129 13 87 28 -10 -13 168 128 140 1 152 52 88 99 107 88 81 176 18 73 29 93 165 50 146 13...

output:

419
136
345
312
338
1
490
557
177
84
50
688
315
784
141
244
stay with parents
53
408
218
764
451
127
371
823
805
349
552
167
523
stay with parents
500
3
52
411
51
699
422
435
278
187
134
252
585
108
583
44
55
109
310
167
879
712
stay with parents
336
311
108
stay with parents
51
434
stay with parent...

result:

ok 1000 lines

Test #6:

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

input:

1000 1000
210 201 195 208 191 209 201 195 201 192 199 200 205 188 200 198 197 207 189 199 194 197 206 186 198 204 203 187 200 201 197 197 191 197 192 191 192 188 189 194 197 191 192 182 184 195 192 183 200 193 193 193 192 190 190 194 182 197 180 191 184 181 189 184 186 180 194 197 194 187 196 196 18...

output:

92
92
102
93
89
114
149
105
72
114
87
71
77
171
90
36
127
136
39
165
92
62
157
135
101
82
87
78
136
99
141
73
109
141
23
73
76
112
58
110
105
97
84
181
19
100
127
76
108
109
49
150
165
159
152
101
108
94
25
87
67
78
127
56
37
50
161
131
142
40
47
73
117
169
87
157
109
121
59
75
184
80
67
82
48
61
65...

result:

ok 1000 lines

Test #7:

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

input:

1000 1000
1000 998 998 998 997 994 994 992 991 991 991 989 987 987 987 986 984 983 982 982 981 979 978 976 975 974 973 972 973 971 969 968 968 968 965 964 963 963 963 960 961 959 957 958 956 955 955 952 951 951 950 949 950 948 947 947 945 943 944 942 940 940 940 938 938 936 936 935 932 932 930 931 9...

output:

598
365
299
422
294
499
645
316
469
475
612
702
612
344
324
424
597
418
241
488
471
618
640
946
673
350
728
925
628
315
389
499
314
216
215
692
600
149
283
826
648
415
639
666
849
273
536
683
339
747
564
380
483
368
555
471
500
959
364
337
441
648
655
342
542
605
676
386
643
80
628
581
149
544
560
9...

result:

ok 1000 lines

Test #8:

score: 0
Accepted
time: 2ms
memory: 7804kb

input:

1000 1000
1 3 2 4 4 6 7 7 10 9 10 12 12 14 14 15 18 19 18 21 21 23 23 23 24 27 27 29 28 29 31 31 33 33 34 36 37 38 38 39 41 41 42 43 44 46 46 49 49 49 50 52 52 55 55 56 58 59 59 59 60 63 64 63 65 65 68 69 69 70 72 71 72 73 76 77 77 79 80 81 82 83 82 83 86 86 88 87 90 89 91 93 93 95 94 97 98 98 98 10...

output:

783
72
634
21
295
234
337
241
823
69
52
39
9
209
270
21
478
802
576
49
232
145
583
516
361
46
519
651
150
459
195
204
31
602
553
266
10
656
398
98
331
584
29
332
296
357
198
595
241
239
401
414
543
288
144
283
187
277
222
803
732
503
2
195
620
481
320
155
438
276
59
142
538
684
127
192
446
243
491
2...

result:

ok 1000 lines

Test #9:

score: 0
Accepted
time: 176ms
memory: 31980kb

input:

200000 200000
4700652 -5734778 3503665 -6188002 8657410 2276806 -6431469 9627247 9673670 9221683 -3908423 -3069613 -653905 2608836 -4959288 -3108645 2053787 -5840353 259545 9847990 2267414 4231267 8319662 9920009 1973822 3854711 9434531 5938280 -5348422 -4062145 -5060918 -3946777 -7934092 7908462 83...

output:

531534449
60349244
698110493
683183122
239017077
155761236
198479042
224389969
53360136
280044750
690025597
359180266
155492131
100215867
7489229
371149856
257552128
756373561
625758735
10281065
33154057
331682245
187783019
356644222
284214063
184871804
232220709
282778596
659349476
574267601
271559...

result:

ok 200000 lines

Test #10:

score: 0
Accepted
time: 133ms
memory: 31940kb

input:

200000 200000
1000000000 1000000000 1000000000 994665379 991463472 993592249 990545330 1000000000 1000000000 993709443 993048450 993175969 1000000000 1000000000 1000000000 1000000000 996652523 1000000000 992737565 1000000000 995381198 999029778 994486837 1000000000 1000000000 1000000000 993523414 99...

output:

435875275
457648009
211124733
489445386
272681020
170279466
457584046
180315969
724633614
337953745
382261536
544196655
49729496
125390351
80990952
414848358
237788201
264980067
590869611
767628306
442404587
573389407
358308533
673491043
546282286
623796355
310334534
305536304
643892535
451194211
31...

result:

ok 200000 lines

Test #11:

score: 0
Accepted
time: 123ms
memory: 31688kb

input:

200000 200000
999936527 1000000000 1000000000 999911064 1000000000 999931025 999987503 999873607 999979442 999867372 999998797 999903420 999942880 999836369 999961944 999997043 999859703 1000000000 999872353 999967979 999895588 999873633 999989612 999939739 999929350 999959172 999826478 999898163 99...

output:

685852606
779027428
767670633
407552348
429157344
536572435
820750082
343199906
153240019
172312558
696380287
469815009
494985027
476719828
619352415
34133816
684452544
206679853
506577503
272757735
230547389
483884971
511887454
396592355
161362798
407519861
605254754
258882877
746577675
73817816
75...

result:

ok 200000 lines

Test #12:

score: 0
Accepted
time: 253ms
memory: 33992kb

input:

200000 200000
29091 38973 -43929 -59096 85131 -48337 55517 -33006 114388 88422 7767 -40627 51481 72946 50475 -11447 34620 163684 152282 17662 127085 117685 96487 130743 48134 216283 135263 86053 82895 96458 120002 55804 119261 211075 164992 157722 254034 265948 189624 138315 217932 180546 277174 157...

output:

243257560
912832934
310015430
101031560
763481383
163629518
514370005
76106312
84131976
6965181
562147379
643978961
377798707
623798585
726189886
624382491
700519954
442408520
215468449
128115935
259664291
514835375
319905852
89344678
414911644
447441446
407846688
188468274
273723302
73973026
385489...

result:

ok 200000 lines

Test #13:

score: 0
Accepted
time: 167ms
memory: 32008kb

input:

200000 200000
478661126 262135998 865858988 810996444 591942227 735500821 501689749 50371518 517447906 446463295 608437123 167043833 827378253 748574239 756186328 580692189 517172087 443374960 523720487 881889997 117184442 337424808 411056272 500688800 480471810 143343364 535362952 859590020 5707259...

output:

272999720
315747073
257419408
189314016
356413659
147502771
180971112
483448182
426842843
378086080
176669194
80835598
216151657
369651435
384795439
496220857
86118937
348241535
444535257
387577828
147119493
342572677
34041459
330955795
468414923
484368631
268057725
393103897
58717209
282747703
3721...

result:

ok 200000 lines

Test #14:

score: 0
Accepted
time: 148ms
memory: 31952kb

input:

200000 200000
294832171 -327658233 662058359 -810653343 -625990848 120657884 -976742718 729067584 -794355628 -907624514 -18150063 881125723 60482279 562743356 -401926055 135101492 -933157390 831548262 344876913 312305225 605857917 170214669 -806582706 -796932016 988860514 -674531379 -806347473 -3319...

output:

stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with pa...

result:

ok 200000 lines

Test #15:

score: 0
Accepted
time: 326ms
memory: 42384kb

input:

200000 200000
-115 5684 9666 14889 19500 24791 29979 35076 39517 44226 49871 55618 60521 65324 70881 75009 80102 85772 90581 95968 100435 105969 110891 115806 120783 124075 129105 134658 140322 144984 150821 155933 160753 165985 170677 174002 180757 184590 189474 194645 200562 205274 209745 214890 2...

output:

487754816
148845568
533460296
274270708
334714248
516345330
122364942
464210262
586120601
753660346
824860348
298260873
296325973
477055095
361450664
206315763
91844684
138950455
147594323
399949576
533145826
306884304
335329718
313459627
750359129
79690485
537295793
877189280
664030013
266225862
64...

result:

ok 200000 lines

Test #16:

score: 0
Accepted
time: 107ms
memory: 30728kb

input:

200000 200000
999999438 999994121 999990963 999984265 999979994 999975607 999970032 999964839 999959530 999954639 999949517 999945232 999939568 999934480 999930947 999925049 999920728 999914933 999910428 999904124 999899891 999894253 999890668 999885182 999879535 999874719 999870139 999864703 999860...

output:

442837499
247532495
768915002
592024999
313189997
323892498
830032502
749387498
559512500
449432498
629235000
577270000
640277500
497827500
599900004
817349998
299582492
669992500
384737501
464914999
723607499
795402502
639147500
316219989
109647500
469607499
563704999
357369999
629572500
639892501
...

result:

ok 200000 lines

Test #17:

score: 0
Accepted
time: 181ms
memory: 31988kb

input:

200000 200000
191 199 206 199 197 201 204 206 205 193 209 202 195 202 205 208 208 206 207 191 205 192 196 196 201 202 190 192 200 206 190 205 191 200 191 195 205 194 204 190 204 208 205 210 200 193 196 194 195 192 205 209 206 200 199 202 199 191 195 195 205 190 197 202 194 191 204 197 208 199 196 18...

output:

40
67
19
50
40
96
22
75
20
58
53
74
19
58
39
134
86
82
16
4
65
9
31
74
69
28
74
17
80
46
85
52
21
15
65
81
77
34
71
44
48
71
49
50
24
96
121
159
104
96
103
41
32
51
3
23
10
46
96
65
50
81
39
103
101
94
78
34
104
104
99
32
17
103
190
98
46
65
99
24
47
91
143
11
13
84
34
44
70
60
68
68
48
12
55
94
154...

result:

ok 200000 lines

Test #18:

score: -100
Wrong Answer
time: 145ms
memory: 32036kb

input:

200000 200000
1059 1069 994 1089 1010 932 1019 981 991 1036 1037 1055 1098 967 924 940 979 1021 1040 1010 998 1092 1012 930 946 997 986 1007 912 918 917 1040 955 905 918 964 968 901 995 1016 1011 1005 1092 1051 990 981 1060 1081 1070 985 1081 1087 1038 1078 961 1092 1077 1098 913 1027 1035 954 1009 ...

output:

143
491
717
733
354
712
579
552
346
451
759
794
282
226
235
663
669
154
378
294
388
223
537
735
875
368
662
856
315
765
652
778
391
315
494
574
379
396
785
609
557
371
522
382
333
794
254
272
682
560
620
455
541
517
531
600
66
563
602
648
732
161
55
644
668
59
494
507
301
563
324
218
339
465
544
913...

result:

wrong answer 56720th lines differ - expected: 'stay with parents', found: '0'