ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#214414 | #2767. 摆烂 | Filberte | 70 | 7125ms | 95680kb | C++11 | 2.4kb | 2024-11-18 20:33:12 | 2024-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...