UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214398#2767. 摆烂ThySecret0408ms49600kbC++111.8kb2024-11-18 19:56:112024-11-19 08:30:30

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[N][21], 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]);
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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: 0
Time Limit Exceeded

Test #32:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Subtask #5:

score: 0
Time Limit Exceeded

Test #42:

score: 0
Time Limit Exceeded

input:

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

output:


result: