QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#774867 | #9786. Magical Bags | ucup-team1004# | RE | 848ms | 59472kb | C++14 | 1.4kb | 2024-11-23 14:05:42 | 2024-11-23 14:05:45 |
Judging History
answer
#include<bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
const int N=2e5+10,M=N*30,MX=1e9;
int n,m,rt,ans,l[N],r[N],len;
vector<int> v[N];
pair<int,int> t[N];
set<int> t1,t2;
map<int,int> t3,t4;
namespace seg
{
int t[M],ls[M],rs[M],cnt;
void modify(int l,int r,int &x,int w,int a)
{
if(!x) x=++cnt;
t[x]=max(t[x],a);
if(l==r) return;
if(w<=mid) modify(l,mid,ls[x],w,a);
else modify(mid+1,r,rs[x],w,a);
}
int query(int l,int r,int x,int w)
{
if(l>w||!x) return 0;
if(r<=w) return t[x];
return max(query(l,mid,ls[x],w),query(mid+1,r,rs[x],w));
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&m);
v[i].resize(m),ans+=min(m,2);
l[i]=MX,r[i]=0;
for(int j=0;j<m;j++)
scanf("%d",&v[i][j]),l[i]=min(l[i],v[i][j]),r[i]=max(r[i],v[i][j]);
t1.insert(l[i]),t2.insert(r[i]);
t3[l[i]]++,t4[r[i]]++;
}
for(int i=1;i<=n;i++)
{
if((int)v[i].size()==1) continue;
if(t3[l[i]]==1) t1.erase(l[i]);
if(t4[r[i]]==1) t2.erase(r[i]);
int L=0,R=MX;
auto k=t2.upper_bound(l[i]);
if(k!=t2.end()) R=*k;
k=t1.lower_bound(r[i]);
if(k!=t1.begin()) L=*--k;
for(auto x:v[i])
if(L<x&&x<R) t[++len]={r[i],l[i]};
t1.insert(l[i]),t2.insert(r[i]);
}
sort(t+1,t+len+1);
for(int i=1;i<=len;i++)
seg::modify(1,MX,rt,t[i].first,seg::query(1,MX,rt,t[i].second)+1);
printf("%d\n",ans-seg::t[1]);
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 12044kb
input:
4 3 4 7 10 2 1 9 4 11 2 8 14 3 6 12 13
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 2ms
memory: 12080kb
input:
4 1 1 1 2 1 3 1 4
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 0ms
memory: 12100kb
input:
4 3 4 7 10 2 1 9 4 11 2 8 14 3 6 12 13
output:
7
result:
ok 1 number(s): "7"
Test #4:
score: 0
Accepted
time: 0ms
memory: 12148kb
input:
4 1 1 1 2 1 3 1 4
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 2ms
memory: 12048kb
input:
100 4 372861091 407948190 424244630 359746969 6 568180757 527358812 494745349 665803213 674832670 586694351 4 696340797 775899164 919971335 716827187 4 123145962 344250363 122030550 251739234 4 342654413 368648894 150539766 255189030 1 194505887 3 755984448 736803561 745474041 4 709314938 498953418 ...
output:
177
result:
ok 1 number(s): "177"
Test #6:
score: 0
Accepted
time: 0ms
memory: 11980kb
input:
100 5 128474911 128789041 128389100 128571722 128449204 4 190783009 179144907 191954599 169739385 7 922968028 923017780 923012667 922993373 923012653 923010830 922983606 1 399117777 8 693609160 693615962 692956804 692902832 694104582 693605539 693750551 692909362 4 133590022 156691169 120354087 1477...
output:
175
result:
ok 1 number(s): "175"
Test #7:
score: 0
Accepted
time: 0ms
memory: 12100kb
input:
100 3 667874577 779650612 311873157 4 315088665 510831928 558038267 371108692 9 755153639 761562353 770756971 766146687 755341778 756786965 752029435 762376276 769269467 6 104846116 127832365 303763622 308914288 193368850 212600340 4 278400790 520739777 691975492 363532266 3 882063076 834874749 8790...
output:
188
result:
ok 1 number(s): "188"
Test #8:
score: 0
Accepted
time: 2ms
memory: 12076kb
input:
100 3 906356952 850278493 852337285 4 171262913 167082071 210705401 185031512 7 802495630 790288362 821278829 774987331 774050880 798490416 758938148 5 15709100 243583562 406822217 439043410 105298894 3 615900896 610909553 657678763 4 829696557 810959924 841612668 819869747 6 853997379 864469575 881...
output:
180
result:
ok 1 number(s): "180"
Test #9:
score: 0
Accepted
time: 2ms
memory: 12172kb
input:
100 4 364081200 540650381 353768306 122255830 7 936882622 937778158 941372288 943745873 947703805 938067346 944019473 7 598655091 679073706 723959930 579018281 860392698 852744534 665808681 1 557290205 3 838323287 764154463 864559801 4 952241609 888202173 792726290 886689636 6 653946054 841409940 83...
output:
175
result:
ok 1 number(s): "175"
Test #10:
score: 0
Accepted
time: 2ms
memory: 12128kb
input:
100 1 440195292 6 859787120 847131414 854112709 869067609 839981608 845676179 5 206450888 209708811 207370111 201853766 207539046 1 555976272 1 938758019 1 413646308 9 252799098 254947888 265345550 249752370 261338550 251583211 248642444 266900460 261558897 5 83936282 116530372 99708225 112074514 96...
output:
151
result:
ok 1 number(s): "151"
Test #11:
score: 0
Accepted
time: 2ms
memory: 12004kb
input:
100 1 146185204 6 852896086 841680008 855876871 835965157 843755423 851708745 1 629541324 6 85793267 91650449 93510560 99883657 85654258 98526112 3 495860961 497537876 493169484 5 454856746 450383319 452706190 450318327 452142745 6 183708510 180433221 182527046 181726412 181810362 181409052 4 692428...
output:
145
result:
ok 1 number(s): "145"
Test #12:
score: 0
Accepted
time: 0ms
memory: 12064kb
input:
100 5 689258498 593041024 495586014 514329370 820761943 7 205596594 194826463 204043065 193869609 214940002 212820377 193426959 7 765457074 564861616 742278670 649051551 719680647 625298040 628377100 7 964607721 975206807 980916305 899670280 950317349 907764973 966416652 14 583444762 587440679 37759...
output:
173
result:
ok 1 number(s): "173"
Test #13:
score: 0
Accepted
time: 0ms
memory: 12112kb
input:
100 4 333222379 411834962 321666960 375921743 6 469180085 599687470 434726418 542075515 468647205 585607083 3 329659185 334204906 442317787 7 407887487 331741182 273383133 416410227 418383971 588307977 271852141 4 865515303 869035169 860812055 861392741 5 641667472 860601686 753823004 793512791 9956...
output:
178
result:
ok 1 number(s): "178"
Test #14:
score: 0
Accepted
time: 0ms
memory: 12220kb
input:
100 7 690642381 613166525 688304596 634201428 562397003 633948538 679003753 4 47850900 39815477 89901918 122900559 1 531415583 6 138747627 198265925 498060210 473915860 275869244 10468108 6 855057160 887426020 927043300 863676485 864198874 851240046 5 692386595 513354859 610032533 595928682 63699127...
output:
175
result:
ok 1 number(s): "175"
Test #15:
score: 0
Accepted
time: 838ms
memory: 56024kb
input:
200000 1 158728811 3 820213140 695694229 890491786 2 223397517 576636349 3 886287626 840274568 787379583 2 531893033 375811452 4 208941903 362012920 456886582 677484638 2 658936887 741915526 1 163021123 3 102990858 99833598 128050246 2 880927685 395844417 2 582184019 506099921 2 503081931 890511277 ...
output:
371392
result:
ok 1 number(s): "371392"
Test #16:
score: 0
Accepted
time: 827ms
memory: 56740kb
input:
200000 4 527049088 576020440 539124238 528502432 4 103304993 110505705 218405655 9254609 2 531392825 552345130 2 153934319 348864359 3 326816216 71550071 319235642 2 672438614 577449099 1 987667909 4 350329232 455028270 302082072 522653010 4 897538960 713329535 762632225 710820739 3 514060771 339989...
output:
371318
result:
ok 1 number(s): "371318"
Test #17:
score: 0
Accepted
time: 825ms
memory: 55712kb
input:
200000 3 874943438 546004813 507400569 2 483105021 364422434 2 275411026 254788551 2 708265881 687362339 3 218906620 351275670 268755597 1 467105066 3 819559064 790247463 817165748 1 970131791 4 219377698 221772069 277674473 292495413 1 200146464 2 850141746 908404899 1 309046733 2 311910499 5859450...
output:
371614
result:
ok 1 number(s): "371614"
Test #18:
score: 0
Accepted
time: 832ms
memory: 55404kb
input:
200000 3 93682084 96073317 179761316 2 499962770 162915432 1 999584091 5 939952415 898712858 869060970 942886905 920106350 2 437796243 672698419 2 970505146 993912024 3 871782821 872319087 818304708 2 888310686 959163381 2 38105511 691834614 2 905703817 935917761 2 599540273 825738795 1 344807309 3 ...
output:
371671
result:
ok 1 number(s): "371671"
Test #19:
score: 0
Accepted
time: 811ms
memory: 56632kb
input:
200000 2 334259130 302821824 3 664423361 720176530 824377961 1 796836198 2 826207789 793267461 3 556670216 454153489 584319445 4 172511854 210668874 139478238 11132315 2 386520917 216809653 2 897449437 759949511 2 773459959 864938043 1 337248305 2 36892453 64751348 4 875441112 883307374 857201990 90...
output:
371431
result:
ok 1 number(s): "371431"
Test #20:
score: 0
Accepted
time: 811ms
memory: 56912kb
input:
200000 3 15180757 211957380 196307347 3 885237955 877473998 891408818 3 527959489 966372326 623116540 2 116250496 196819637 4 749133092 606791247 867630877 756654095 1 433166056 4 922504811 845536998 716730303 836804118 2 780726579 782822569 1 543764901 4 833829333 571953795 776159760 819478189 3 40...
output:
371213
result:
ok 1 number(s): "371213"
Test #21:
score: 0
Accepted
time: 833ms
memory: 55984kb
input:
200000 2 805842744 581609804 2 734227758 733064953 2 989774966 942880204 2 628257088 63946269 2 583848176 911813757 4 691317022 781500071 996319911 435048080 3 794873372 718581447 531638733 3 980221944 947251248 970539493 2 3861235 452095431 3 227824664 425339258 400130407 1 744456362 2 75860498 428...
output:
371418
result:
ok 1 number(s): "371418"
Test #22:
score: 0
Accepted
time: 824ms
memory: 56324kb
input:
200000 4 765248606 58641312 461505864 48058936 3 530497192 74608066 187318400 2 760807063 462798246 3 829369025 850399705 861318513 1 610260849 4 840112564 619362793 672743435 984829729 2 254124774 801464441 3 762528829 691988008 647617371 4 158351130 690785043 135019901 441491859 1 88740299 4 97607...
output:
371430
result:
ok 1 number(s): "371430"
Test #23:
score: 0
Accepted
time: 848ms
memory: 56408kb
input:
200000 3 260017688 247206101 245341550 3 528907971 401175380 519150579 2 751738818 699510603 2 761128342 838467598 1 671361404 4 951730690 940117575 944967225 934430806 3 273582273 423597064 390919521 3 800578214 757476170 793151055 4 154531575 169715009 226492241 234234388 3 791708466 641989170 684...
output:
371722
result:
ok 1 number(s): "371722"
Test #24:
score: 0
Accepted
time: 838ms
memory: 55952kb
input:
200000 2 77875703 98417625 1 580863835 3 328175215 539412729 441689644 4 519986810 532514024 524724699 522062026 4 495150066 502888818 208873688 519737098 1 467977355 2 481764791 265552887 3 514214795 546606435 874871364 4 157881601 327298118 568566685 173899494 1 408646380 1 248681217 2 803252090 9...
output:
371459
result:
ok 1 number(s): "371459"
Test #25:
score: 0
Accepted
time: 743ms
memory: 58120kb
input:
200000 3 617019209 617017532 617017307 3 970339026 970356059 970348843 3 558398372 558216433 558343400 2 346653959 346876820 1 281458709 1 967860014 4 475956654 475955112 475982395 475983808 3 499143819 499137223 499221662 4 723910593 723909360 723829452 724024083 3 519143186 519253790 519321105 1 5...
output:
365869
result:
ok 1 number(s): "365869"
Test #26:
score: 0
Accepted
time: 712ms
memory: 59472kb
input:
200000 3 576685712 576687248 576688432 3 767079880 767012338 767023712 2 809256364 809272790 3 394124992 394073184 394092525 2 759516270 759428114 1 895219353 3 438371420 438426848 438410444 2 310767315 310839932 1 202464867 2 603282846 603356839 1 782566135 2 650736061 650648190 3 647048066 6470414...
output:
357282
result:
ok 1 number(s): "357282"
Test #27:
score: 0
Accepted
time: 704ms
memory: 57572kb
input:
200000 2 982301221 982233632 2 911767146 911829091 2 486037419 485943061 3 505146942 505224831 505204823 1 632133123 1 489557731 2 703344129 703366051 2 650398414 650390190 3 394534473 394580673 394585491 3 126075457 125986865 126013358 3 794657480 794590085 794642851 3 787812105 787818979 787840359...
output:
361549
result:
ok 1 number(s): "361549"
Test #28:
score: 0
Accepted
time: 812ms
memory: 55944kb
input:
200000 3 913660216 914036470 913841789 3 317845899 317670209 318337619 3 94610832 94539407 94537481 3 369813385 369465271 369523389 1 68655150 2 361720346 361397713 2 841915577 842209587 3 656553414 656388735 656706235 3 612612056 612998341 613140059 1 621038044 2 349678682 348811194 2 221887705 221...
output:
370229
result:
ok 1 number(s): "370229"
Test #29:
score: 0
Accepted
time: 780ms
memory: 56264kb
input:
200000 1 5642826 3 461063276 460468925 460613639 2 640527131 640588995 2 671932901 672143977 1 903027019 3 540766029 540483743 540269503 2 207757030 208217727 4 861139257 861051707 861078118 861077332 2 481255334 480974330 4 362981126 362943325 363022442 362988716 3 32203238 31650608 31764601 3 2866...
output:
369419
result:
ok 1 number(s): "369419"
Test #30:
score: 0
Accepted
time: 811ms
memory: 57692kb
input:
200000 2 505843259 505239454 3 723724918 723066584 723626111 1 86353949 2 214624116 214296544 3 167340181 167349779 167349587 2 350159908 350055188 3 379611811 379777377 379736400 2 876593838 876020897 2 963121551 963616157 2 936958144 937428994 2 689150609 688504031 2 9155490 8854750 2 609202639 60...
output:
370156
result:
ok 1 number(s): "370156"
Test #31:
score: 0
Accepted
time: 776ms
memory: 56820kb
input:
200000 2 421023837 420532799 3 531618132 531445793 531709271 1 916087065 2 699008541 698624333 2 555767036 555551138 3 620708586 620458919 620677285 2 881807045 881737135 3 486057243 485868230 485677837 2 507150411 507385192 3 89817461 89710261 89983728 3 290522225 290842137 290675086 2 705362131 70...
output:
368946
result:
ok 1 number(s): "368946"
Test #32:
score: 0
Accepted
time: 764ms
memory: 56544kb
input:
200000 2 905633261 905206014 3 575923853 575782402 576003616 1 575598461 1 834510366 3 144611707 144515175 144650402 1 384852119 4 205355179 205334200 205501346 205449577 2 270991591 271127063 2 495751300 495484348 4 678430204 678417774 678431544 678361285 2 445073250 444680651 3 480881024 481306492...
output:
368270
result:
ok 1 number(s): "368270"
Test #33:
score: 0
Accepted
time: 738ms
memory: 58540kb
input:
200000 1 626521854 2 985585113 985627840 3 528981816 529078225 529059028 4 931259243 931256646 931257141 931272876 2 5007153 4940473 1 839142863 2 867034659 866845260 2 953839484 953953044 2 739864025 739996079 2 883921952 884014431 1 261276759 3 527037541 527045605 527036030 2 366891875 366795240 2...
output:
365216
result:
ok 1 number(s): "365216"
Test #34:
score: 0
Accepted
time: 770ms
memory: 57268kb
input:
200000 3 130403137 130366909 130194098 3 444112904 444337243 444072211 2 768086779 767960882 2 406264114 406110368 3 437808387 437884200 438028260 5 978027579 977966850 977965648 978112580 978097916 2 153010807 153103181 3 220787828 221103689 221093744 2 235703371 235785772 4 771852620 771566039 771...
output:
367761
result:
ok 1 number(s): "367761"
Test #35:
score: -100
Runtime Error
input:
200000 5 558945239 558945928 558943942 558945170 558945737 2 389787163 389792339 2 74806397 74808912 2 55617410 55611498 1 324837485 3 754994327 754992763 754989423 2 363304227 363296230 3 808094401 808092569 808094084 3 410017026 410019024 410018730 4 898729558 898732123 898729121 898737342 2 38193...