UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214399#2767. 摆烂ThySecret2012423ms359828kbC++112.0kb2024-11-18 19:59:292024-11-19 08:30:37

answer

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define x first
#define y second
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

inline void debug() { cerr << '\n'; }
template<typename Type, typename... Other>
inline void debug(const Type& x, const Other&... y) { cerr << x << ' '; debug(y...); }
#define DEBUG(a...) cerr << "[" << #a << "] = ", debug(a);

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2000010;
const int INF = 2e16;

template<typename Type>
inline void read(Type &res)
{
    res = 0;
    int ch = getchar(), flag = 0;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    res = flag ? -res : res;
}
template<typename Type, typename... Other>
inline void read(Type &res, Other&... y) { read(res), read(y...); }

int n;
PII a[N];
int f[21][N], dp[N];

void Init()
{
    // for (int i = 1; i <= n; i ++) f[i][0] = a[i].y;
    // for (int k = 1; k < 21; k ++)
    //     for (int i = 1; i + (1 << k) - 1 <= n; i ++)
    //         f[i][k] = max(f[i][k - 1], f[i + (1 << k - 1)][k - 1]);
    for (int i = 1; i <= n; i ++) f[0][i] = a[i].y;
    for (int k = 1; k < 21; k ++)
        for (int i = 1; i + (1 << k) - 1 <= n; i ++)
            f[k][i] = max(f[k - 1][i], f[k - 1][i + (1 << k - 1)]);
}

inline int Query(int l, int r)
{
    int k = __lg(r - l + 1);
    // return max(f[l][k], f[r - (1 << k) + 1][k]);
    return max(f[k][l], f[k][r - (1 << k) + 1]);
}

signed main()
{
    read(n);
    for (int i = 1; i <= n; i ++) read(a[i].x, a[i].y);
    Init();

    for (int i = 1; i <= n; i ++)
    {
        int l = 1, r = i - 1, res = 0;
        while (l <= r)
        {
            int mid = l + r >> 1;
            if (dp[mid] <= a[i].x) res = mid, l = mid + 1;
            else r = mid - 1;
        }
        dp[i] = a[i].x + 2 * Query(res + 1, i);
    }
    cout << dp[n] << '\n';

    return 0;
}

详细

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

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 10
Accepted
time: 8ms
memory: 32428kb

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: 0ms
memory: 32428kb

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: 0ms
memory: 32428kb

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: 32428kb

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: 5ms
memory: 32428kb

input:

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

output:

2878920725

result:

ok 1 number(s): "2878920725"

Test #6:

score: -10
Wrong Answer
time: 0ms
memory: 32428kb

input:

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

output:

1333333330

result:

wrong answer 1st numbers differ - expected: '888888906', found: '1333333330'

Subtask #2:

score: 0
Wrong Answer

Test #8:

score: 20
Accepted
time: 7ms
memory: 32524kb

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: 4ms
memory: 32524kb

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: 0ms
memory: 32520kb

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

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: 32520kb

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: 32524kb

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: 4ms
memory: 32520kb

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: 0ms
memory: 32524kb

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: 4ms
memory: 32520kb

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: 0ms
memory: 32520kb

input:

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

output:

2999420445

result:

ok 1 number(s): "2999420445"

Test #18:

score: -20
Wrong Answer
time: 4ms
memory: 32524kb

input:

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

output:

1333333330

result:

wrong answer 1st numbers differ - expected: '888889886', found: '1333333330'

Subtask #3:

score: 0
Wrong Answer

Test #20:

score: 20
Accepted
time: 19ms
memory: 45516kb

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: 27ms
memory: 45512kb

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: 21ms
memory: 45512kb

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: 28ms
memory: 45512kb

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: 12ms
memory: 45516kb

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: 23ms
memory: 45516kb

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: 22ms
memory: 45516kb

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: 25ms
memory: 45512kb

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: 33ms
memory: 45512kb

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: 29ms
memory: 45512kb

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: -20
Wrong Answer
time: 23ms
memory: 45512kb

input:

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

output:

1333333330

result:

wrong answer 1st numbers differ - expected: '888988886', found: '1333333330'

Subtask #4:

score: 20
Accepted

Test #32:

score: 20
Accepted
time: 609ms
memory: 359828kb

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: 523ms
memory: 359828kb

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: 641ms
memory: 359828kb

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: 574ms
memory: 359824kb

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: 531ms
memory: 359824kb

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: 616ms
memory: 359828kb

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: 621ms
memory: 359824kb

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: 606ms
memory: 359824kb

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: 702ms
memory: 359828kb

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: 507ms
memory: 359828kb

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
Wrong Answer

Test #42:

score: 30
Accepted
time: 621ms
memory: 359824kb

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: 508ms
memory: 359824kb

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: 583ms
memory: 359828kb

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: 515ms
memory: 359824kb

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: 589ms
memory: 359824kb

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: 461ms
memory: 359828kb

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: 528ms
memory: 359828kb

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: 766ms
memory: 359828kb

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: 520ms
memory: 359828kb

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: 577ms
memory: 359828kb

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
Wrong Answer
time: 516ms
memory: 359828kb

input:

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

output:

1333333330

result:

wrong answer 1st numbers differ - expected: '890888886', found: '1333333330'