QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#440673 | #8522. Waterfall Matrix | ucup-team3586# | TL | 5298ms | 42896kb | C++23 | 4.4kb | 2024-06-13 22:34:34 | 2024-06-13 22:34:36 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
#define ls (x<<1)
#define rs (ls|1)
void die(string S){puts(S.c_str());exit(0);}
int n,a[200200],b[200200],c[200200],ans[200200];
vector<int> poolx,pooly;
vector<pii> vy[200200];
// vector<pii> helper[200200];
int xx[200200],yy[200200];
pii *helper[200200];
int Pos[200200];
int tag[200200<<2],tagmx[200200<<2],mx[200200<<2],mxpos[200200<<2];
void build(int x,int l,int r)
{
tag[x]=mx[x]=0;
tagmx[x]=-inf;
mxpos[x]=l;
if(l==r) return ;
int mid=(l+r)/2;
build(ls,l,mid);
build(rs,mid+1,r);
}
void pushdown(int x,int l,int r)
{
if(!tag[x]&&tagmx[x]<-1e6) return ;
mx[x]=max(mx[x]+tag[x],tagmx[x]);
if(l!=r)
{
tag[ls]+=tag[x];
tag[rs]+=tag[x];
tagmx[ls]=max(tagmx[ls]+tag[x],tagmx[x]);
tagmx[rs]=max(tagmx[rs]+tag[x],tagmx[x]);
}
tag[x]=0;
tagmx[x]=-inf;
}
void pushup(int x,int l,int r)
{
int mid=(l+r)/2;
pushdown(ls,l,mid);
pushdown(rs,mid+1,r);
mx[x]=max(mx[ls],mx[rs]);
if(mx[ls]==mx[x])
mxpos[x]=mxpos[ls];
else
mxpos[x]=mxpos[rs];
}
void add(int x,int l,int r,int ql,int qr,int v)
{
pushdown(x,l,r);
if(ql<=l&&r<=qr)
{
tag[x]+=v;
tagmx[x]+=v;
return ;
}
int mid=(l+r)/2;
if(ql<=mid)
add(ls,l,mid,ql,qr,v);
if(qr>mid)
add(rs,mid+1,r,ql,qr,v);
pushup(x,l,r);
}
void setmx(int x,int l,int r,int ql,int qr,int v)
{
pushdown(x,l,r);
if(ql<=l&&r<=qr)
{
tagmx[x]=max(tagmx[x],v);
return ;
}
int mid=(l+r)/2;
if(ql<=mid)
setmx(ls,l,mid,ql,qr,v);
if(qr>mid)
setmx(rs,mid+1,r,ql,qr,v);
pushup(x,l,r);
}
pii query(int x,int l,int r,int ql,int qr)
{
pushdown(x,l,r);
if(l==ql&&r==qr)
return mp(mx[x],mxpos[x]);
int mid=(l+r)/2;
if(qr<=mid) return query(ls,l,mid,ql,qr);
if(ql>mid) return query(rs,mid+1,r,ql,qr);
return max(query(ls,l,mid,ql,mid),query(rs,mid+1,r,mid+1,qr));
}
void solve(vector<int> &vec,int L,int R)
{
if(!sz(vec)) return ;
if(L==R)
{
for(auto x:vec)
ans[x]=L;
return ;
}
int mid=(L+R)/2;
poolx.clear();
pooly.clear();
for(auto ind:vec)
poolx.pb(a[ind]);
for(auto ind:vec)
pooly.pb(b[ind]);
srt(poolx);
uni(poolx);
srt(pooly);
uni(pooly);
int N=sz(poolx),M=sz(pooly);
for(int i=0;i<=N;i++)
{
vy[i].clear();
// helper[i].clear();
}
for(auto ind:vec)
{
int x=xx[ind]=ub(poolx,a[ind]);
vy[x].pb(yy[ind]=ub(pooly,b[ind]),(c[ind]>mid?1:0));
}
for(int i=0;i<=N;i++)
srt(vy[i]);
build(1,1,M+1);
for(int i=1;i<=N;i++)
{
static int vpos[1<<20];
int sz=0;
for(auto pr:vy[i])
add(1,1,M+1,1,pr.first,(pr.second?-1:1));
// vector<int> vpos;
// vpos.pb(0);
vpos[sz++]=0;
for(auto pr:vy[i])
vpos[sz++]=pr.first;
// vpos.pb(pr.first);
// vpos.pb(M+1);
vpos[sz++]=M+1;
// helper[i].resize(sz(vy[i])+1);
delete helper[i];
helper[i]=new pii[sz(vy[i])+1];
pii cur=mp(-inf,-inf);
for(int j=sz-1;j;j--)
{
helper[i][j-1]=cur;
setmx(1,1,M+1,vpos[j-1]+1,vpos[j],cur.first);
cur=max(query(1,1,M+1,vpos[j-1]+1,vpos[j]),cur);
}
}
pii pr=query(1,1,M+1,1,M+1);
int val=pr.first,pos=pr.second;
for(int i=N;i>=1;i--)
{
int label=0;
while(label<sz(vy[i])&&vy[i][label].first<pos)
label++;
if(val==helper[i][label].first)
pos=helper[i][label].second;
Pos[i]=pos;
for(auto pr:vy[i])
if(pos<=pr.first)
val+=(pr.second?1:-1);
}
vector<int> V1,V2;
for(auto ind:vec)
{
int x=xx[ind];
int y=yy[ind];
if(y>=Pos[x])
V1.pb(ind);
else
V2.pb(ind);
}
solve(V1,L,mid);
solve(V2,mid+1,R);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i]>>c[i];
vector<int> vec;
for(int i=1;i<=n;i++)
vec.pb(i);
solve(vec,1,1000000000);
ll ans=0;
for(int i=1;i<=n;i++)
ans+=abs(::ans[i]-c[i]);
cout<<ans<<endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 18136kb
input:
5 1 3 5 3 2 1 3 3 3 4 4 1 3 5 4
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 17968kb
input:
1 1 1 58383964
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 3ms
memory: 15916kb
input:
2 1 1 204909414 2 2 807091086
output:
602181672
result:
ok 1 number(s): "602181672"
Test #4:
score: 0
Accepted
time: 3ms
memory: 17960kb
input:
4 2 4 107744934 3 2 143843719 4 4 908851567 2 2 307161330
output:
801106633
result:
ok 1 number(s): "801106633"
Test #5:
score: 0
Accepted
time: 0ms
memory: 18116kb
input:
7 1 2 140766572 5 3 795389698 3 6 279722536 2 6 442413348 4 2 475716910 5 4 704493410 5 2 423494885
output:
935621651
result:
ok 1 number(s): "935621651"
Test #6:
score: 0
Accepted
time: 3ms
memory: 15908kb
input:
11 1 5 104443431 4 9 692130290 4 1 18812720 7 3 381505729 7 7 706418558 11 9 242808397 10 4 490383412 3 2 72839501 10 7 883914647 10 6 738589165 11 10 556539693
output:
2757182575
result:
ok 1 number(s): "2757182575"
Test #7:
score: 0
Accepted
time: 0ms
memory: 15864kb
input:
17 14 13 957289906 14 1 220840920 10 3 230060608 9 12 405076666 13 5 112827045 12 12 925699151 11 9 243364659 3 15 66125969 1 5 481618704 17 11 67207393 9 4 141885319 2 2 641760683 4 6 30421350 5 9 145177348 7 13 468875688 11 7 557989385 13 17 468110036
output:
3056543193
result:
ok 1 number(s): "3056543193"
Test #8:
score: 0
Accepted
time: 0ms
memory: 15828kb
input:
26 22 1 655039096 18 3 405980640 11 23 310084709 17 6 5210226 6 25 869210460 14 23 9079903 17 9 162692938 21 1 703337421 13 8 216969244 8 23 242760842 11 9 876472951 5 15 545320494 8 6 764694540 4 12 164086724 6 13 394175551 10 1 906738317 26 25 224731347 12 14 967318812 26 14 449256484 23 4 6152281...
output:
3872286425
result:
ok 1 number(s): "3872286425"
Test #9:
score: 0
Accepted
time: 0ms
memory: 15840kb
input:
40 33 19 974202889 40 11 262863105 18 17 143706322 15 37 253303786 4 8 962133788 40 22 885916470 22 19 949122323 32 29 221627390 17 24 605257795 3 14 259799950 5 3 987951246 28 30 451968921 13 17 503334855 11 26 190979064 11 13 497711531 29 4 764544900 38 16 199461325 7 9 618831071 25 30 209848351 1...
output:
7657769074
result:
ok 1 number(s): "7657769074"
Test #10:
score: 0
Accepted
time: 0ms
memory: 17896kb
input:
61 6 25 772410634 9 47 581631393 40 34 565465748 8 55 154525415 3 50 298013089 16 23 593130934 26 5 721815207 42 43 28712243 61 21 539501497 49 53 283028482 4 20 267467572 59 45 55599983 26 3 218043086 15 8 213292621 37 44 119318590 29 33 445273185 37 3 734748198 21 56 178476345 12 40 897802983 3 29...
output:
9305689053
result:
ok 1 number(s): "9305689053"
Test #11:
score: 0
Accepted
time: 0ms
memory: 15876kb
input:
92 67 63 115551817 40 57 922062274 21 83 268857323 59 65 957783695 44 1 720871230 44 65 682393003 85 21 850933251 47 32 990892557 75 90 807656030 37 83 446279042 6 8 121301986 52 34 648749799 29 56 519610045 58 28 915936953 19 8 736754508 77 25 251573087 77 5 708764858 71 66 395892865 37 9 339525762...
output:
20584500053
result:
ok 1 number(s): "20584500053"
Test #12:
score: 0
Accepted
time: 0ms
memory: 17908kb
input:
139 34 89 106739274 76 37 623575790 96 95 241595468 100 37 24819785 67 78 157943133 86 66 173514198 6 107 220712008 95 94 902234730 124 117 827871287 82 10 199132415 48 29 821720496 99 15 21336498 79 84 287004315 27 57 112113016 102 106 99696275 52 94 326387056 17 41 717541828 24 119 561086579 137 1...
output:
34223480997
result:
ok 1 number(s): "34223480997"
Test #13:
score: 0
Accepted
time: 5ms
memory: 15976kb
input:
209 202 11 985436507 81 23 303372005 58 65 271936110 105 6 780231383 183 131 67052291 140 15 742761772 92 31 934033938 172 97 238586287 77 191 267962930 199 10 970201899 2 150 211701369 35 162 119938268 195 197 567498864 62 159 198698620 17 110 472437657 202 179 121800271 115 135 70371572 111 62 443...
output:
49909325408
result:
ok 1 number(s): "49909325408"
Test #14:
score: 0
Accepted
time: 3ms
memory: 15864kb
input:
314 26 307 692391292 279 111 226570582 290 76 261494858 132 47 708283863 253 177 82612833 32 26 881275895 248 213 349235000 240 136 227630771 133 208 894493845 295 174 760101024 191 182 333036912 309 205 326571720 138 220 582371900 185 262 33941275 113 151 91998856 194 51 532523590 219 174 90194801 ...
output:
73980124774
result:
ok 1 number(s): "73980124774"
Test #15:
score: 0
Accepted
time: 4ms
memory: 16140kb
input:
472 215 64 888756595 191 437 782953525 284 151 807803141 142 382 737321722 200 373 933468526 387 190 414005694 137 464 157330847 240 55 838395267 262 74 996210474 428 42 179226852 364 446 789614149 177 66 882599216 6 278 229756157 22 325 676675321 231 131 811796299 335 86 632795653 184 433 454696152...
output:
115815454982
result:
ok 1 number(s): "115815454982"
Test #16:
score: 0
Accepted
time: 13ms
memory: 16076kb
input:
709 507 296 959229221 564 579 785837067 165 238 854583076 195 550 409079670 134 411 35472127 581 210 191747703 170 161 804804474 111 106 442762676 488 333 310679628 69 505 273768286 120 85 205745581 652 565 468876379 30 165 512567322 236 654 568944218 572 116 598480208 448 537 315385253 590 374 4940...
output:
176997131937
result:
ok 1 number(s): "176997131937"
Test #17:
score: 0
Accepted
time: 16ms
memory: 18312kb
input:
1064 1011 964 184314429 821 627 456155208 732 497 56527680 179 168 52071168 836 1005 604045343 19 401 439301716 818 500 303713286 970 268 24075641 888 744 839729821 101 97 726134962 942 260 735986500 143 436 241015562 668 910 391605524 634 635 160559352 205 50 612020502 20 360 696670729 175 575 2551...
output:
266930542461
result:
ok 1 number(s): "266930542461"
Test #18:
score: 0
Accepted
time: 24ms
memory: 16384kb
input:
1597 639 1393 166904194 1326 984 426206306 443 1524 935852282 848 1091 771776465 760 898 864783022 1379 372 38647886 481 603 346594658 521 122 293597610 1441 1589 133798182 1185 1272 279881925 544 666 231802145 1081 429 975793623 802 720 31278767 918 535 992962940 528 706 915212950 520 505 309874112...
output:
405559254752
result:
ok 1 number(s): "405559254752"
Test #19:
score: 0
Accepted
time: 48ms
memory: 16344kb
input:
2396 1981 1533 298355427 97 1737 959008541 787 1377 213392751 471 1 315600441 1995 1605 255228530 1813 309 900206470 463 536 734537574 730 2056 946098919 42 535 656307145 213 2365 598200890 582 105 100509217 1413 1740 655194157 1152 17 689800494 2106 1978 135105427 1252 999 617607068 1044 612 802184...
output:
597231143545
result:
ok 1 number(s): "597231143545"
Test #20:
score: 0
Accepted
time: 71ms
memory: 16624kb
input:
3595 1226 458 449847735 3424 1750 313050010 3169 2627 640096567 162 1184 906369956 1422 1015 293642622 340 2940 990712500 1026 1217 841244511 388 3004 899853656 896 669 146375886 2674 2297 111706208 3201 1696 323055839 351 1670 182429627 1633 511 12020195 2001 3285 41275714 248 1703 219345489 1759 1...
output:
899911898812
result:
ok 1 number(s): "899911898812"
Test #21:
score: 0
Accepted
time: 111ms
memory: 18696kb
input:
5393 2093 1287 583196596 2605 4403 533046343 3917 285 235297421 4318 4681 411844255 1588 1842 648962599 2164 2375 680797189 217 3854 531509369 4606 3646 354560797 4059 1754 976303595 1979 2652 265487574 4518 3955 157233712 2220 3416 107520029 1693 4855 722727994 4784 4162 245866252 498 1215 20109583...
output:
1349936604836
result:
ok 1 number(s): "1349936604836"
Test #22:
score: 0
Accepted
time: 194ms
memory: 16940kb
input:
8090 4866 7478 356775584 2504 3192 239406790 7743 2941 65392868 5615 1820 337863138 7340 4815 69744983 6191 1229 587983387 7729 3212 685050434 4313 5380 999113456 6515 5715 447059187 2429 7934 458547204 3870 7822 238996790 2286 3953 479733208 2620 3563 480862876 1111 6631 522438482 7956 2469 1939648...
output:
2064278617120
result:
ok 1 number(s): "2064278617120"
Test #23:
score: 0
Accepted
time: 328ms
memory: 17728kb
input:
12136 9194 7715 385468038 10307 6421 156181299 2779 9831 370946156 5449 7750 978449190 1276 844 367495644 1009 11917 41206130 4623 821 884083711 7802 3252 270221800 11699 9720 67880248 905 7498 882641163 846 10014 591139488 6648 1671 688996597 4295 12118 207178901 4320 10134 122002645 3686 10730 854...
output:
3119930013408
result:
ok 1 number(s): "3119930013408"
Test #24:
score: 0
Accepted
time: 498ms
memory: 20336kb
input:
18205 15502 9773 287504909 99 3826 342956061 5281 2167 882347909 11920 6288 432122804 12016 16973 61123860 5295 1207 911757865 14111 7883 777996097 1347 9620 363217200 660 15969 710395355 13065 15291 668428361 11892 17197 764778250 5172 9857 283025751 10253 11454 797309399 854 16916 387603881 4046 9...
output:
4646485106348
result:
ok 1 number(s): "4646485106348"
Test #25:
score: 0
Accepted
time: 795ms
memory: 21508kb
input:
27308 24579 3661 862768022 5266 18066 445716653 23679 2988 969489642 19312 17314 795242288 4196 16999 888385325 4082 25785 490546658 20278 6999 217961913 23575 3413 63174645 23253 26512 938455547 11715 7880 24996012 12751 25040 156918854 10141 15211 698329456 21632 8801 287594181 8346 4485 864856860...
output:
6953369240363
result:
ok 1 number(s): "6953369240363"
Test #26:
score: 0
Accepted
time: 1343ms
memory: 21728kb
input:
40963 32397 21728 665533394 14092 25532 885841420 6996 13499 541070446 10132 14170 968034413 34862 23452 27553808 4384 18087 951007362 40193 36533 876771802 21939 255 835996912 14813 34602 396870817 23518 12878 121167193 24674 35802 634701100 30982 21854 872559058 37114 1857 748537081 14651 28035 78...
output:
10475585732428
result:
ok 1 number(s): "10475585732428"
Test #27:
score: 0
Accepted
time: 1982ms
memory: 26100kb
input:
61445 36697 25963 94951597 7513 24837 819005409 854 59947 670876395 53706 28155 500385795 21808 12434 384290319 22180 9978 226530813 24817 39062 431206958 29985 44370 903111841 33782 7850 744209998 40702 37285 53291120 25414 271 438279520 4742 2959 465420139 4122 48945 880775407 42032 3922 82058901 ...
output:
15678557202606
result:
ok 1 number(s): "15678557202606"
Test #28:
score: 0
Accepted
time: 3351ms
memory: 32308kb
input:
92168 56230 42965 742064775 4877 45898 159393199 59960 15737 139858988 83885 3886 29974986 7528 23740 133054240 42731 67896 795632101 65960 85613 760855118 22584 18115 872879663 74322 5174 466635717 16877 65430 512235721 42196 12741 698697046 13205 45782 999285629 9991 85074 537703269 11324 57987 99...
output:
23527389016280
result:
ok 1 number(s): "23527389016280"
Test #29:
score: 0
Accepted
time: 5298ms
memory: 41024kb
input:
138253 137028 98027 420176109 80718 126363 925205029 6738 78045 403027262 61401 88129 15744684 23837 119097 640220864 15996 46921 935267867 55975 15608 132891604 113324 22647 47973513 6441 33699 644316078 25548 66322 765816467 122863 55030 252850483 98023 67850 575671984 60006 91757 240693176 74046 ...
output:
35424061451157
result:
ok 1 number(s): "35424061451157"
Test #30:
score: 0
Accepted
time: 5032ms
memory: 41396kb
input:
131071 90672 123987 228449234 3604 102308 987422594 59810 25149 860613161 104850 269 689330493 24993 101682 976691697 78019 43297 520816902 71433 76386 821164796 5909 77441 120378040 45000 43490 35922905 17468 78999 878299743 1241 113223 90941807 110893 103555 180500551 91339 77238 493814644 13139 5...
output:
33473411344075
result:
ok 1 number(s): "33473411344075"
Test #31:
score: 0
Accepted
time: 4917ms
memory: 37540kb
input:
131072 61466 60099 43713848 4432 107280 858182963 105411 3399 116715084 97176 123606 720509750 25188 78189 197911350 63294 23532 650834189 29931 114646 773415808 83011 103448 15006743 36024 52158 574964066 104377 4278 481207906 98234 14071 880195643 95198 110017 473546968 90133 59609 136208461 322 5...
output:
33464721182174
result:
ok 1 number(s): "33464721182174"
Test #32:
score: 0
Accepted
time: 5268ms
memory: 42896kb
input:
131073 45917 103829 958666723 94319 91112 870672821 76150 4477 607817071 116729 95377 688420221 63089 57400 798542306 96986 104154 423949112 122218 10852 946616129 82316 122347 621862025 76160 94630 657810973 128606 83099 974721993 36605 86452 897502490 47480 70841 125116337 126918 109172 170092230 ...
output:
33570691146219
result:
ok 1 number(s): "33570691146219"
Test #33:
score: -100
Time Limit Exceeded
input:
199995 15467 44256 880189728 11879 82576 277886095 88467 171050 502781139 34306 134775 937105286 128255 122988 6045953 191726 128000 120294449 184032 174614 229445343 39848 120710 778565003 164709 140201 284867637 170121 23229 628225839 83381 194905 423440701 105958 129062 548268870 157416 169550 53...
output:
51069618351288