ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214398 | #2767. 摆烂 | ThySecret | 0 | 408ms | 49600kb | C++11 | 1.8kb | 2024-11-18 19:56:11 | 2024-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 ...