UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214394#2767. 摆烂ThySecret033ms48784kbC++111.8kb2024-11-18 19:49:102024-11-19 08:30:07

answer

#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];

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);
    sort(a + 1, a + 1 + n, [](const PII &a, const PII &b) { return a.x < b.x; });
    Init();

    // int ans = INF;
    // for (int i = 1; i < n; i ++)
    // {
    //     int res = max(a[n].x, a[i].x + Query(1, i) * 2) + Query(i + 1, n) * 2;
    //     ans = min(ans, res);
    // }
    // ans = min(ans, a[n].x + 2 * Query(1, n));
    // // DEBUG(Query(1, n));
    // cout << ans << '\n';

    return 0;
}

Details

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

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 32376kb

input:

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

output:


result:

wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements

Subtask #2:

score: 0
Wrong Answer

Test #8:

score: 0
Wrong Answer
time: 8ms
memory: 32544kb

input:

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

output:


result:

wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements

Subtask #3:

score: 0
Wrong Answer

Test #20:

score: 0
Wrong Answer
time: 22ms
memory: 48784kb

input:

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

output:


result:

wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements

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: