Luogu4085 [USACO17DEC]Haybale Feast （线段树，单调队列）（未完成）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int  a = (b); a <= (c); ++ a)
#define nR(a,b,c) for(register int  a = (b); a >= (c); -- a)
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Abs(a) ((a) < 0 ? -(a) : (a))
#define Swap(a,b) a^=b^=a^=b
#define ll long long

#define ON_DEBUG

#ifdef ON_DEBUG

#define D_e_Line printf("\n\n----------\n\n")
#define D_e(x)  cout << #x << " = " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt","r",stdin);

#else

#define D_e_Line ;
#define D_e(x)  ;
#define Pause() ;
#define FileOpen() ;

#endif

struct ios{
    template<typename ATP>ios& operator >> (ATP &x){
        x = 0; int f = 1; char c;
        for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-')  f = -1;
        while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
        x*= f;
        return *this;
    }
}io;
using namespace std;

const int N = 100007;

int n;

#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
int t[N << 2];
inline void Pushup(int rt){
    t[rt] = Max(t[rt << 1], t[rt << 1 | 1]);
}
inline void Updata(int rt, int l, int r, int x, int w){
    if(l == r){
        t[rt] = w;
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid)
        Updata(lson, x, w);
    else
        Updata(rson, x, w);
    Pushup(rt);
}
inline int Query(int rt, int l, int r, int L, int R){
    if(L <= l && r <= R){
        return t[rt];
    }
    int mid = (l + r) >> 1, maxx = 0;
    if(L <= mid) maxx = max(maxx, Query(lson, L, R));
    if(R > mid)  maxx = max(maxx, Query(rson, L, R));
    return maxx;
}

long long sum[N];
int main(){
FileOpen();
    int Val;
    io >> n >> Val;
    R(i,1,n){
        int x, y;
        io >> x >> y;
        sum[i] = sum[i - 1] + x;
        Updata(1, 1, n, i, y);
    }
    
    int ans  = 2147483647;
    R(l,1,n){
        R(r,l,n){
            if(sum[r] - sum[l - 1] >= Val){
                int newAns = Query(1, 1, n, l, r);
                ans = Min(ans, newAns);
            }
        }
    }
    
    printf("%d", ans);
    
    return 0;
}
/*
1000 344532178460
859533823 62461389
177370849 364557107
484299804 663783698
594669676 224351394
62686259 227217756
993678784 852733389
991990877 401367851
917175177 325573270
635099420 48484527
814824791 257045418
141356988 669983734
145533846 3475789
571732989 200767622
334049965 855508497
206517193 600880796
549153302 808565328
441517016 314481899
509632821 160296488
705723899 549379709
808872344 72249871
360368651 812024414
499875265 447543388
316730885 757756702
949831349 495784265
708321669 186685335
523848102 705839438
736157827 951299619
20450902 120917991
873104574 512806864
288966161 119991833
274447569 919160251
509612171 886973761
768345774 768254207
874790854 936835816
195519677 449223026
107817460 685593976
660368482 617589278
608293412 491465537
553044611 711552861
290729063 758064916
293003264 325855477
743190958 467189076
670550300 504589235
488565587 418096405
761793601 167548593
602346101 392999146
522370608 569659720
536217477 292011304
53485043 201211432
906665635 859110157
378076522 972254175
983134673 805260690
573422243 674763785
578500016 117557120
595435945 218124192
806246508 632869214
46061370 491009237
865043092 314957054
472169899 807408425
597295629 335328702
823701237 193359874
33411339 281237697
578126397 280585124
972762337 423584945
344654342 842130035
357688457 863160443
929087376 817931095
58710939 218324528
21605280 195204617
35066121 945776369
608484224 477217351
956913807 345313463
23897309 62621971
872967906 363311435
949711153 623142144
530090184 389812909
767097583 191002717
802263575 667827336
147489536 660502914
643345947 135168584
218342239 702191570
891103970 233469612
568029966 241077420
988882258 768166073
457244115 131610016
97552197 335259829
445445537 475138514
317841687 99661497
374116734 424568854
71502033 217559731
640511730 818857119
885458474 912632228
656042339 922539472
115054926 992858982
774246595 85354765
982086289 364948381
738122145 679595716
839378502 614397568
661717754 746217085
183662733 885552792
538105407 883929529
537249110 450789555
299249235 75182968
785964875 539733025
681914235 886065430
942977378 191468783
669943842 489382870
48448123 371301048
28467951 645741000
197887508 516911173
351440717 10359546
996254038 111612604
833318743 773509691
356687109 139640363
581936428 965008555
569702089 427169674
281679015 51496890
308817331 898649142
435741010 579910397
841313045 916007064
834405045 777376405
303029462 258690570
190339374 356958208
833844530 141109291
622900726 109722757
975321342 483117443
435869120 585579923
619003934 114582443
759804335 19951460
994100697 427640819
396609252 22458076
108808220 157428120
456815169 438498955
837019155 689308412
237065507 777802561
686324258 917136169
188772186 860783483
202705056 954812050
658009365 696357329
262573886 399014
185400637 29725859
989260924 689954594
132851970 533800330
225010374 30645048
303222071 274652966
195857466 757733631
354843679 295625234
50443546 622370477
394526081 444074851
927314586 13678800
702322130 284164771
454572143 320924795
394086925 579372724
240831174 716608647
530046799 734383037
805492984 183671400
582896630 996996216
907038411 681897044
335726901 48734211
858930562 660871997
660549909 445607397
223650673 800470458
889304844 60329988
481859745 455901378
612628550 337694309
538137386 347658758
666553774 420826639
728979876 570569797
289471958 30987424
893079434 149088128
184607815 663410210
68358329 713080456
859530701 9989935
691073268 203110477
499081344 59076800
667152866 826089472
81925689 388037296
516909389 51006985
372447706 887505561
249839506 722047457
947117392 622416438
74730487 791103338
994793019 252328211
366071076 15925677
52950094 873991597
534546166 119574738
425089438 873824317
704874921 239258572
321795991 836398132
221637319 248034712
400288930 663513879
229992346 10794622
55682193 621489483
355183008 630010216
121607931 533797793
793859794 85658947
766336650 286895264
884614770 691151209
868927306 98682115
38318150 841794774
661048528 235962342
669316166 677458976
311731454 484182118
598755522 175688412
980037633 292925341
712286646 254060717
250426465 923382555
653616215 948862697
387532637 868160095
484423914 602216821
573435171 892053085
814330132 533246193
231511522 847523714
989184682 482297124
272073028 738688730
488650516 771747881
786519121 191269135
788589695 631676405
406864618 585694275
614372036 649434276
444895724 898116238
366032130 435102079
28748338 488645390
946001209 547139099
845304034 346824306
834803691 102845602
962088755 347585199
130653449 90479882
571234274 408790801
525828096 697602067
733333308 724249020
340452458 14284175
178992681 779133540
794698582 224525158
88622623 200515567
643090438 135796115
658988113 637070128
895468081 566639191
502194620 774237227
589875573 180490632
766661695 381217462
279374232 89068549
543336530 756592666
433193755 717868552
764443276 677213151
311863238 551592159
673781276 560626698
314852886 332748794
922925254 330361697
464871839 555490287
84830251 886628773
204151182 563789792
430310066 570089586
746541800 454816599
522498848 577497350
629694181 470687651
692603319 148873870
809688190 899280115
72950725 943414462
402715459 644005893
242767330 119943903
551208704 993968390
496476081 225774545
226113345 314676049
611117325 708339498
371359728 855470314
390583948 760646981
12809663 543632938
230872164 839252043
369890504 858276083
980324952 826928480
938194093 329442954
26581352 76184488
57936462 928016340
778292889 445691546
55419749 505552065
445610430 25278098
649453071 772120016
382647234 512272493
632364333 250767325
578815315 48069892
202470035 226031170
379202186 593417630
450473064 147180746
849372434 4954806
605938339 638209499
800745660 926025291
673368039 57811783
402870594 30125964
474013983 662423735
743716041 206925320
788815714 135410444
628391318 48305680
368403670 565127389
207659880 478676785
757020382 474685219
127563194 765921852
796765334 600679266
476425451 389777118
710225079 879816778
84015522 78380352
595718372 669915890
589525185 733970457
736250511 361555960
188651759 984242138
137686116 176921970
531140035 854789490
507424560 627017683
377602995 559351677
124427334 674872184
83304116 206357827
99739411 209294194
49459708 193140967
808790150 838307364
590999663 819468666
646983833 73834647
641906454 637671674
695851947 897061580
28168820 986955400
422491779 164642444
540866398 43265032
996693605 554348461
693809392 18248134
985457377 114507752
969244971 363014875
685603602 616230836
741670285 183642580
53276814 996465519
707882161 316067144
678492503 285332351
560519328 711328131
574295843 324981860
692931321 292894366
104386988 26730238
146367704 59475086
619654923 318336331
823714287 412682820
656636004 162848892
498984386 506925564
132481659 752434294
138147730 419075703
497380812 399202933
664410766 910513182
276954698 106804414
378761995 711320257
500026840 847580766
40850771 457874577
710077501 705932928
359134709 474255866
831586446 649823246
175331661 451662743
13273370 820963722
686687986 587861724
855112928 922406769
212452273 493789174
917022835 986386746
17596709 468886701
457138820 509392194
586732737 979609191
635167044 111299271
607465658 538047765
749136272 36692740
193592469 270901278
694672968 573717857
488356646 127650488
431019440 681378346
875438803 15746197
741005062 814408081
505031297 131885508
271334534 137988534
359117146 179074525
811536112 818783884
794675035 902504149
846517737 344444384
627941902 11155329
432784022 273936962
862567023 575596488
874074030 700326503
17943072 921500524
956809944 747180072
112877149 898174539
678271712 869456905
800479694 750902023
584399908 492794202
975761416 363248397
805220248 968498162
651109507 694560861
130596669 209920246
453653979 995478203
919198296 332942686
632547182 102693401
69900081 137098055
304529508 773910155
540021226 870853160
749915759 252628867
144952003 961850320
258661996 825256841
330676161 664889996
886835673 436904108
630307947 48834578
21346806 145999393
499921487 150663122
589884331 327686338
148591160 921886483
486337338 548879284
900868948 70947459
9646539 724835639
638141334 708067420
861504226 966769905
787616798 386323878
234193830 831909279
494677392 59979580
212805494 901309497
972463970 777639893
335740212 272460592
721661394 118270562
911226546 204921638
896950440 784584964
19602009 885967272
428413339 904053602
7302647 329020250
469210968 468778989
439323040 653554894
300240095 622448039
836139397 935601235
453013236 963928837
729504255 793873062
734877509 907831463
28610842 899817986
132727128 583072887
431985114 805333911
862169046 329239586
401747705 485091767
550682070 732773744
476936215 384244674
486145566 546984347
366049115 720568974
343760035 843889412
774684908 516348135
890657475 245420912
534591400 879814172
900283202 963732672
642670492 593956458
955403593 732950529
726231399 547815269
986205276 873277783
718425004 342228567
7210405 926184200
795563231 798028792
879271221 2686113
344368055 325471720
263768954 758554067
980763860 687454068
38153133 215837702
943418253 85070547
350359611 93813600
514426099 190283071
220471164 421208229
472849202 413302291
560228929 125559432
312555882 381708212
72022244 370811420
623929868 226634772
702027006 692724821
939208840 204426607
128570038 508079784
615869198 42423843
235098382 352868431
993832080 207953791
839556836 390440039
377850125 417898293
40336411 402969049
142454964 870046963
458099691 552632142
15723716 128006231
942213715 241486624
527298200 709578055
87023344 164970598
978580909 505818610
871484043 120087934
25590198 597719983
747914533 977770240
101594906 256085777
211547784 324419676
502754740 524497655
696306298 107807756
108265746 703735610
581866402 861831800
353826932 387027581
656537214 649977412
220934886 253403339
490474511 289127368
766324283 79043095
560965575 695200292
222472971 334194170
695402431 307349537
562779427 42106378
4800373 149232249
535443214 163866541
720964400 72192603
567075129 299267717
837246814 220597527
948186148 762178469
322017844 495105265
86114294 992694600
746805654 594451887
436881409 419251970
663154718 201217496
552794545 803660893
164225179 616088655
369604401 344718660
86406161 529394152
710723505 825903921
150458029 86090657
259443906 8174505
982163872 595144039
450395534 991617683
358189147 688322685
486098005 821368444
202711246 783437170
925072336 982888696
538513400 224875115
902768506 858305884
849598066 575917956
62979381 858751916
444756704 709082341
711588662 334212091
226705250 599146972
657950669 783587077
687377648 367850900
134537897 951888008
20721645 376336701
711685532 888564358
491203389 728219855
663284023 226954581
161963418 183635350
207907299 342072221
350746703 157226306
194551333 280392770
601339211 650068092
382794900 846619712
769593213 259116607
868822991 492943557
453637354 716053425
488649192 749503816
583921455 159494655
38459159 448193464
568584134 965052812
807910357 10261715
953229350 697670427
465554324 214847220
819506820 564753706
616224744 649384751
906970617 616233513
11957033 172124233
693477245 878296043
751593292 529646990
243939588 346373393
454438250 218077195
956373984 936193117
942452182 827236169
547527019 319180938
940485684 189498841
902705762 877517703
279105938 829206515
915777589 458631871
314105815 661628379
26985156 420467375
903827678 406207092
489443661 143500594
915449963 320939210
201215570 617082789
366206393 142714849
800980383 576055862
490222892 355125725
819085078 992720273
937226905 180033187
298327910 696601045
37394948 357915885
439818966 398648588
483775012 433530739
851171915 184052511
401033962 300364821
755196161 953524157
489846572 472774830
814434586 141312521
83508473 146342397
377338528 409422102
810025937 133334599
49721441 297120204
89068720 181875081
435489900 654471921
59874760 219002701
495665950 568546534
423999292 805359898
855093420 594544216
127891337 912303732
166705812 432156369
471145815 775506216
388616896 986392142
637759404 731420851
872396383 421400785
707290521 36050075
989322912 658036683
710945020 253939232
517002723 545921296
181645703 271317707
268259155 854386667
254263992 996189434
294507100 904756785
87974156 39140529
574465033 516774996
931092050 150740258
620114626 528380291
980028437 138368169
104414606 402143443
822515963 673545999
813686945 460612116
874318903 520948124
498120500 500361856
669959705 756000714
225535925 273646117
652122880 546451696
878384449 131103042
146817078 95919543
728909382 459510559
79390806 733923252
978196373 485381403
411045793 796726895
29666714 392256094
76300336 332001490
55584144 47321763
474143635 694001252
409591495 245426007
54550591 929999088
846586900 433125102
779997198 98975271
340478460 451299789
208206009 863237239
6981603 301942860
964685598 675357056
15662134 166730977
356419616 802531327
839190626 677999510
385818345 122052299
546841321 605814711
213580470 128034926
384770489 764347506
985577735 655093410
426571609 14868550
237334902 463929428
872135635 333984847
839173997 398515907
333276023 732767185
688522692 285244181
258701112 408937629
772375497 850073788
225520009 6145905
481525250 202753031
706647863 707265727
210976816 391836912
883115997 197335339
190352630 579751800
994812693 582997533
444844272 33354070
546915517 779085059
943193121 596235913
942975268 156006013
410969273 853154156
772358913 571346500
468043845 180295551
68161895 988177011
714546989 662681696
375341722 135108592
27380521 622907586
569503284 307071106
222044452 648259698
119195194 785124731
461563970 794710826
883112705 141998291
712390222 921129129
714303617 867304189
499829873 758390271
94378645 305213206
879750337 538995961
343631840 836799694
237762494 680911415
413962193 689303295
193574128 298204185
479361621 345854023
215592698 661562797
562349131 326314270
776268383 779557556
542564356 663566130
924181840 162524915
231766639 840299435
959242667 831766240
588598688 194729311
899327086 309044701
767921351 77427787
461679951 596519846
367066088 632956605
289346837 75562424
498277443 436503025
751764591 187443813
706968360 635296078
576233757 683247753
176719958 162450305
290899744 405466609
839947440 512870526
958285085 843812919
86024956 564941061
705868643 834608470
636484802 784013104
192038839 115690779
969888965 449203798
505844398 912780537
879882462 612137189
72320489 14714421
792738643 569826913
729955352 859267577
967536512 639973697
928918968 134981486
724700700 591160940
433282128 55669916
684493071 205138915
51598273 702514343
571555638 441246432
585111119 634957420
95930279 613713676
689664991 156519055
984194197 359069558
501849028 334590004
958576671 375781300
798375810 824403811
710913588 799403432
908739757 285390032
112807550 802174373
490668884 334720505
681798732 18548332
830318096 807492863
957910774 995218883
610265477 349965464
374997204 787245507
409717920 222767335
215001876 395285451
263228821 270481727
986594221 967825457
975106506 93594262
280949480 675112431
731356960 793764712
776688906 331086449
35752140 664537644
319021440 600417345
885521613 900067578
604605114 779266814
849166365 836512013
742794960 832452709
474810191 85647885
530230845 606410285
997953484 756914115
887675921 600308538
304675932 13624449
621459955 590746501
583942352 318843274
560297875 210584627
206110487 207823995
89945440 958256012
680769167 968260377
81749131 641852461
6283701 383464004
901670191 652536678
79109661 303694934
893533378 262340575
295799115 71083000
257323809 882934629
135330491 314380064
293471595 680901830
137788639 826275804
486550733 914183579
251295096 490078243
925089218 192882646
283790962 113509944
124236852 694666680
854718669 738555100
42461232 681347017
967373518 48025589
685621848 922891358
990751065 409281021
766956553 38135353
969153998 981523715
855878739 908498767
438334614 147206465
318820483 444158516
85588463 744995975
522727127 119215209
562044069 567837950
697607600 503954000
416653102 818245867
277211832 133488258
924829977 130778050
799789353 959509298
367682236 251146210
335362311 363521022
995330158 690097200
519936920 468854797
532436204 90923579
28531514 640302517
651004718 7105558
664781703 702408804
321912963 879853945
76781518 903034599
52078303 180443965
153525050 93905076
118096550 573826022
37165242 792222841
787706457 819480868
484369328 758523339
671406261 372205466
172736379 856172933
208498090 607820146
645875099 766695132
379777448 598161249
767741130 269670507
242342742 351719855
693087544 771050680
7244704 428914073
336432115 90114254
866760651 190933529
642770501 127324074
854617816 117260553
66854064 482306267
905256686 801224431
114628672 271258945
732719985 79805770
401563579 611703152
836265495 907446674
397104676 832848076
850307385 686282330
850560798 650435731
909707779 448808433
252521629 703332131
965485773 532950079
959695735 930287352
541414821 670675805
339679950 989385924
903019597 783433430
901949216 837739573
737076516 285578289
34947327 22939031
321777454 749837829
61374099 722322930
47766609 728246905
21520602 919505118
718112696 461977129
584824677 115694020
830194414 876261539
444403868 147676807
853465483 77352645
573440557 982575587
386431749 767848512
897882069 336346214
374682043 859043697
258099757 335154956
834847809 702718189
511651388 800355528
415141540 109493677
232169911 101907578
779974752 795467173
355592539 265090229
997241251 597582546
825972843 791278093
638460824 709026733
29855182 338603896
16601180 916899974
826508367 128145146
7091342 807191521
810976383 1361572
106841039 381013581
209765634 436604088
249781756 825176627
573651079 225843143
456240855 449679968
338198851 792608568
755707406 956075881
440548922 855850618
235055025 273636519
746596869 306627862
189962998 473666121
283872407 408614235
217977413 441137287
901293453 763152053
418203014 24079667
43465933 387495951
85148649 869234841
99563403 472344805
591336633 40464112
294177663 736626647
769883161 837305349
966092545 955916709
284282846 864411567
370300430 231709601
29296369 610310217
721260720 757475549
59610807 77703520
803944743 467673272
6894870 991696572
814771280 431419461
925151933 173183424
865392201 813722900
70072161 881762968
935873611 443947323
975964028 547322810
312337621 687707053
180752875 297943040
838289677 568126792
94713238 560008639
414856698 690863301
417688657 159492819
404531197 22593174
679253285 186893543
841062927 88107820
679968441 395351973
124745194 648436086
60514799 238719939
366244995 791490260
744281060 39523242
281090581 899113291
489454368 323444739
604073956 442028896
376323485 529471980
500231172 771751633
893076028 91851890
200304246 332845850
168954070 637673156
413578779 687706734
793847329 949901516
48344604 778940862
152066176 270671699
308654223 304776633
515959541 193030598
85618713 179665901
595672571 973880307
91072122 567047563
871653723 824424451
462399629 880987934
5546826 883699358
135234888 855064090
97744269 961923750
932788309 742477860
333101208 275171580
440086040 592394012
983333283 922081893
984587982 534971516
873267030 21979385
360781402 232946110
792709174 74541430
724251963 565422542
597136293 878585617
435527254 208547179
198699929 212627215
282790425 477362164
796141869 859521246
490519405 161065483
88352178 154084772
44587104 977405949
631972192 102512882
925488921 468231623
827206853 56447693
764638617 739092271
395990203 355511365
708911350 433777491
707868947 93979446
13306883 310474890
11582448 318933483
301139288 702790857
914583555 791597079
199502066 809250295
879602549 202606692
425326711 566712738
996360285 823572513
588478579 323532591
5125859 250966333
113441727 723360573
603969646 836374373
80990673 779342333
342625717 33026189
545389290 897591634
846753105 5298663
424943464 567922946
241852036 694358701
596080145 307783760
164085183 410667933
951074210 983454446
118832968 65893063
383628627 900417292
469305191 978651530
801899146 985311670
938390007 400944081
398470082 158915005
*/
/*
996465519
*/#include <iostream>
#include <cstdio>
#include <