UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214414#2767. 摆烂Filberte707125ms95680kbC++112.4kb2024-11-18 20:33:122024-11-19 08:32:44

answer

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 2e6 + 100;
namespace IO{
    const int SI = (1 << 21) + 5;
    char IB[SI], *IS = IB, *IT = IB;
    //#define gc() (IS == IT ? ((IT = (IS = IB) + fread(IB, 1, SI, stdin), IS == IT) ? EOF : *IS++) : *IS++)
    #define gc() getchar()
    inline int read(){
        int x = 0, fg = 1;
        char ch = gc();
        while(ch < '0' || ch > '9'){if (ch == '-') fg = -1;ch = gc();}
        while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + ch - '0';ch = gc();}
        return x * fg;
    }
    inline void write(int x){
        if(x < 0) putchar('-'), x = -x;
        static int sta[70];
        int tp = 0;
        do{sta[tp++] = x % 10, x /= 10;}while(x);
        while(tp) putchar(sta[--tp] + '0');
        putchar('\n');
    }
}
using namespace IO;

int n, cnt;
struct Segment_Tree{
    int Mn[N << 2];
    Segment_Tree(){memset(Mn, 0x3f, sizeof(Mn));}
    int qry(int u, int l, int r, int L, int R){
        if(L > R) return Mn[0];
        if(L <= l && r <= R) return Mn[u];
        int mid = (l + r) >> 1;
        if(R <= mid) return qry(u << 1, l, mid, L, R);
        if(L > mid) return qry(u << 1 | 1, mid + 1, r, L, R);
        return min(qry(u << 1, l, mid, L, R), qry(u << 1 | 1, mid + 1, r, L, R));
    }
    void upd(int u, int l, int r, int p, int k){
        if(l == r){
            Mn[u] = min(Mn[u], k);
            return ;
        }
        int mid = (l + r) >> 1;
        if(p <= mid) upd(u << 1, l, mid, p, k);
        else upd(u << 1 | 1, mid + 1, r, p, k);
        Mn[u] = min(Mn[u << 1], Mn[u << 1 | 1]);
    }
}T;
pair<int, int> val[N];
int f[N];
int32_t main(){
    n = read();
    for(int i = 1;i <= n;i++){
        int x = read(), y = read();
        while(cnt > 0 && y > val[cnt].second) cnt--;
        val[++cnt] = {x, y};
    }
    n = cnt;
    f[0] = 0;T.upd(1, 0, n, 0, f[0] + 2 * val[1].second);
    for(int i = 1;i <= n;i++){
        int t = val[i].first;
        int lft = 1, rit = i - 1, pos = 0;
        while(lft <= rit){
            int mid = (lft + rit) >> 1;
            if(f[mid] <= t) pos = mid, lft = mid + 1;
            else rit = mid - 1;
        }
        f[i] = min(T.qry(1, 0, n, pos + 1, i - 1), val[i].first + 2ll * val[pos + 1].second);
        if(i == n){
            write(f[n]);
            break;
        }
        T.upd(1, 0, n, i, f[i] + 2 * val[i + 1].second);
    }
}

Details

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

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 7ms
memory: 94896kb

input:

20
12513359 382258501
49946422 294259408
61782741 259996549
128874560 457675284
152578248 511428369
...

output:

2781551734

result:

ok 1 number(s): "2781551734"

Test #2:

score: 0
Accepted
time: 12ms
memory: 94892kb

input:

20
6592046 616393821
8538879 124771654
24979050 168650283
59952328 506075107
128878498 796836890
168...

output:

2878186356

result:

ok 1 number(s): "2878186356"

Test #3:

score: 0
Accepted
time: 12ms
memory: 94896kb

input:

20
2099663 147467539
25290040 156795746
197254068 590585918
198843927 512239904
222920966 456981246
...

output:

2770880243

result:

ok 1 number(s): "2770880243"

Test #4:

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

input:

20
66393530 420843093
90129695 489656570
131248562 182208891
291691534 751771331
342922878 673384475...

output:

2926027520

result:

ok 1 number(s): "2926027520"

Test #5:

score: 0
Accepted
time: 8ms
memory: 94896kb

input:

20
141852945 69130050
155003677 784901688
156591867 730149439
161520357 619098795
188670057 61380271...

output:

2878920725

result:

ok 1 number(s): "2878920725"

Test #6:

score: 0
Accepted
time: 3ms
memory: 94900kb

input:

20
0 333333333
1 333333332
2 333333331
3 333333330
4 333333329
5 333333328
6 333333327
7 333333326
8...

output:

888888906

result:

ok 1 number(s): "888888906"

Test #7:

score: 0
Accepted
time: 8ms
memory: 94900kb

input:

20
0 200000000
1 199999999
2 199999998
3 199999997
4 199999996
5 199999995
6 199999994
7 199999993
8...

output:

799218728

result:

ok 1 number(s): "799218728"

Subtask #2:

score: 20
Accepted

Test #8:

score: 20
Accepted
time: 0ms
memory: 94892kb

input:

1000
132699 718470029
234343 395421925
1290414 393017296
1399642 607415822
1402810 515471990
2008288...

output:

2991845504

result:

ok 1 number(s): "2991845504"

Test #9:

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

input:

1000
1460927 635822050
1474184 113973702
2262058 184319286
2754182 45688636
3158543 762355475
357426...

output:

2997073536

result:

ok 1 number(s): "2997073536"

Test #10:

score: 0
Accepted
time: 17ms
memory: 94892kb

input:

1000
2118442 141038751
2135116 387165975
4874198 290249307
6872737 82266843
7401335 726603624
756080...

output:

2995302771

result:

ok 1 number(s): "2995302771"

Test #11:

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

input:

1000
437090 934565437
1175198 156863320
1198404 324764019
2277385 373440655
2425307 392581950
350360...

output:

2995901355

result:

ok 1 number(s): "2995901355"

Test #12:

score: 0
Accepted
time: 4ms
memory: 94892kb

input:

1000
9066 773817477
123486 806680042
851047 596461942
992394 523789453
1003388 520126158
1323726 958...

output:

2992153228

result:

ok 1 number(s): "2992153228"

Test #13:

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

input:

1000
1219327 803904616
2680619 571390377
2920737 199860734
3524708 883722438
4171344 134002719
59874...

output:

2997734121

result:

ok 1 number(s): "2997734121"

Test #14:

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

input:

1000
2880284 488746460
3414969 562543737
4498732 74314414
9375222 111266686
9458421 596112995
963592...

output:

2998591235

result:

ok 1 number(s): "2998591235"

Test #15:

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

input:

1000
1239163 666132179
1871097 706139536
2956078 487495665
3259471 69911742
4479955 188362973
586756...

output:

2996854561

result:

ok 1 number(s): "2996854561"

Test #16:

score: 0
Accepted
time: 8ms
memory: 94892kb

input:

1000
630980 355641503
934118 736144505
1523728 365898752
4057089 829930253
4910133 224420115
4990452...

output:

2999709988

result:

ok 1 number(s): "2999709988"

Test #17:

score: 0
Accepted
time: 4ms
memory: 94892kb

input:

1000
193594 350732868
965625 322880549
1694055 576483511
1992769 754390117
2507741 171984733
3271204...

output:

2999420445

result:

ok 1 number(s): "2999420445"

Test #18:

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

input:

1000
0 333333333
1 333333332
2 333333331
3 333333330
4 333333329
5 333333328
6 333333327
7 333333326...

output:

888889886

result:

ok 1 number(s): "888889886"

Test #19:

score: 0
Accepted
time: 4ms
memory: 94904kb

input:

1000
0 200000000
1 199999999
2 199999998
3 199999997
4 199999996
5 199999995
6 199999994
7 199999993...

output:

799217760

result:

ok 1 number(s): "799217760"

Subtask #3:

score: 20
Accepted

Test #20:

score: 20
Accepted
time: 17ms
memory: 94896kb

input:

100000
9326 430414358
13368 156324232
15149 550951304
22296 345034579
22578 397947033
37137 49312905...

output:

2999984291

result:

ok 1 number(s): "2999984291"

Test #21:

score: 0
Accepted
time: 20ms
memory: 94892kb

input:

100000
1281 980120279
38572 969057410
60961 443629644
67305 918262285
68761 540475664
79259 86368005...

output:

2999973779

result:

ok 1 number(s): "2999973779"

Test #22:

score: 0
Accepted
time: 27ms
memory: 94896kb

input:

100000
20710 863020655
22837 465689267
34425 232297482
37426 410827133
47298 825839625
48599 2328793...

output:

2999991115

result:

ok 1 number(s): "2999991115"

Test #23:

score: 0
Accepted
time: 32ms
memory: 94896kb

input:

100000
1893 587093713
12130 188883761
20509 103771956
23181 427935148
30291 289716104
52036 41982854...

output:

2999953325

result:

ok 1 number(s): "2999953325"

Test #24:

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

input:

100000
9157 466195030
10932 448643920
15616 675011785
24802 20969130
42481 213957558
43201 100624199...

output:

2999986961

result:

ok 1 number(s): "2999986961"

Test #25:

score: 0
Accepted
time: 30ms
memory: 94896kb

input:

100000
8028 735757896
15346 778429486
19608 762797726
36073 700770644
38385 673827857
39670 79333540...

output:

2999964970

result:

ok 1 number(s): "2999964970"

Test #26:

score: 0
Accepted
time: 24ms
memory: 94892kb

input:

100000
18066 489619655
39420 363288479
45624 255823520
53848 768452718
86073 570556759
97457 1152834...

output:

2999949901

result:

ok 1 number(s): "2999949901"

Test #27:

score: 0
Accepted
time: 23ms
memory: 94892kb

input:

100000
9572 354230841
44475 137493766
73724 908871450
83706 376797074
88538 381989371
90425 46309979...

output:

2999992149

result:

ok 1 number(s): "2999992149"

Test #28:

score: 0
Accepted
time: 19ms
memory: 94892kb

input:

100000
2617 628340050
16629 69440544
45392 441060577
52161 702044189
66272 750166177
70981 780473233...

output:

2999978454

result:

ok 1 number(s): "2999978454"

Test #29:

score: 0
Accepted
time: 25ms
memory: 94896kb

input:

100000
1820 854489707
4143 351640051
6324 246260208
10128 483185284
12354 258240070
17250 502913471
...

output:

2999978980

result:

ok 1 number(s): "2999978980"

Test #30:

score: 0
Accepted
time: 47ms
memory: 95676kb

input:

100000
0 333333333
1 333333332
2 333333331
3 333333330
4 333333329
5 333333328
6 333333327
7 3333333...

output:

888988886

result:

ok 1 number(s): "888988886"

Test #31:

score: 0
Accepted
time: 39ms
memory: 95680kb

input:

100000
0 200000000
1 199999999
2 199999998
3 199999997
4 199999996
5 199999995
6 199999994
7 1999999...

output:

799119142

result:

ok 1 number(s): "799119142"

Subtask #4:

score: 20
Accepted

Test #32:

score: 20
Accepted
time: 319ms
memory: 94892kb

input:

2000000
181 24185667
293 532288461
1433 921996635
1694 629544979
2540 173534643
2662 963172401
3159 ...

output:

2999999604

result:

ok 1 number(s): "2999999604"

Test #33:

score: 0
Accepted
time: 315ms
memory: 94892kb

input:

2000000
260 442386156
1749 891768917
1861 616479085
2342 964680659
2627 684052525
2883 384062414
290...

output:

2999998834

result:

ok 1 number(s): "2999998834"

Test #34:

score: 0
Accepted
time: 301ms
memory: 94896kb

input:

2000000
213 424805015
1396 7709726
1506 622452063
1955 116647577
2155 152183545
4125 911447791
4384 ...

output:

2999997514

result:

ok 1 number(s): "2999997514"

Test #35:

score: 0
Accepted
time: 374ms
memory: 94892kb

input:

2000000
35 863105455
513 617091843
1102 710534172
4347 227715846
4961 863805953
5307 68806776
6997 5...

output:

2999997958

result:

ok 1 number(s): "2999997958"

Test #36:

score: 0
Accepted
time: 344ms
memory: 94892kb

input:

2000000
335 51974424
513 624057311
824 935726152
883 899456965
1003 536665976
1343 480024689
1591 34...

output:

2999999056

result:

ok 1 number(s): "2999999056"

Test #37:

score: 0
Accepted
time: 321ms
memory: 94896kb

input:

2000000
1770 876700210
2618 855247437
3117 946298002
3623 950691406
3738 490183040
3968 499286660
41...

output:

2999999048

result:

ok 1 number(s): "2999999048"

Test #38:

score: 0
Accepted
time: 331ms
memory: 94896kb

input:

2000000
312 794196764
814 918957656
1234 187116918
1653 401089556
1997 308069650
2300 483401628
2569...

output:

2999996084

result:

ok 1 number(s): "2999996084"

Test #39:

score: 0
Accepted
time: 395ms
memory: 94896kb

input:

2000000
803 56665060
1243 812188749
1301 489626677
1417 469823961
2208 72225804
2461 304342571
2741 ...

output:

2999999633

result:

ok 1 number(s): "2999999633"

Test #40:

score: 0
Accepted
time: 309ms
memory: 94892kb

input:

2000000
57 298958028
102 487589263
2002 638371165
2064 113138699
2404 37758633
2581 829315955
2666 7...

output:

2999998829

result:

ok 1 number(s): "2999998829"

Test #41:

score: 0
Accepted
time: 332ms
memory: 94896kb

input:

2000000
1846 579002148
1966 487385702
2032 807841592
2751 213874398
4434 228199139
4446 413874427
46...

output:

2999998974

result:

ok 1 number(s): "2999998974"

Subtask #5:

score: 0
Time Limit Exceeded

Test #42:

score: 30
Accepted
time: 318ms
memory: 94892kb

input:

2000000
684 624071334
1181 709831992
1397 43325781
1938 430417709
4157 60566309
4568 912818933
5265 ...

output:

2999999891

result:

ok 1 number(s): "2999999891"

Test #43:

score: 0
Accepted
time: 342ms
memory: 94892kb

input:

2000000
716 961296951
867 587008884
1188 120228907
1362 27242985
1810 872080678
2160 760439837
2603 ...

output:

2999998971

result:

ok 1 number(s): "2999998971"

Test #44:

score: 0
Accepted
time: 303ms
memory: 94892kb

input:

2000000
610 982311315
696 97431714
1316 776011105
2184 994549619
2525 408120441
3477 688756543
3731 ...

output:

2999999031

result:

ok 1 number(s): "2999999031"

Test #45:

score: 0
Accepted
time: 329ms
memory: 94896kb

input:

2000000
246 249824288
1101 244326831
1388 16146229
2009 935786174
2093 748943820
2887 268223777
3013...

output:

2999998952

result:

ok 1 number(s): "2999998952"

Test #46:

score: 0
Accepted
time: 419ms
memory: 94892kb

input:

2000000
161 731248865
172 541182670
183 231702648
2813 248068761
4771 715634312
5616 517828133
5818 ...

output:

2999998701

result:

ok 1 number(s): "2999998701"

Test #47:

score: 0
Accepted
time: 307ms
memory: 94896kb

input:

2000000
825 725030954
1168 381589380
1266 743004857
3740 960593802
3800 277083962
4337 912199250
455...

output:

2999998092

result:

ok 1 number(s): "2999998092"

Test #48:

score: 0
Accepted
time: 319ms
memory: 94896kb

input:

2000000
52 925930364
356 921007272
1299 130822844
2364 660000805
2482 830482938
4148 260844246
4202 ...

output:

2999999007

result:

ok 1 number(s): "2999999007"

Test #49:

score: 0
Accepted
time: 342ms
memory: 94892kb

input:

2000000
1015 396093150
1500 99095065
1604 176343132
1786 539231821
2102 977579393
2255 903370886
238...

output:

2999999413

result:

ok 1 number(s): "2999999413"

Test #50:

score: 0
Accepted
time: 317ms
memory: 94892kb

input:

2000000
1005 453769417
2405 934269622
2718 902248183
3039 177888423
3173 154278677
3757 665695953
39...

output:

2999999797

result:

ok 1 number(s): "2999999797"

Test #51:

score: 0
Accepted
time: 334ms
memory: 94892kb

input:

2000000
1209 723197158
1576 885725297
2560 979809874
2829 634878390
3139 728671424
3571 258053178
41...

output:

2999998345

result:

ok 1 number(s): "2999998345"

Test #52:

score: -30
Time Limit Exceeded

input:

2000000
0 333333333
1 333333332
2 333333331
3 333333330
4 333333329
5 333333328
6 333333327
7 333333...

output:


result: