QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#774867#9786. Magical Bagsucup-team1004#RE 848ms59472kbC++141.4kb2024-11-23 14:05:422024-11-23 14:05:45

Judging History

你现在查看的是最新测评结果

  • [2024-11-23 14:05:45]
  • 评测
  • 测评结果:RE
  • 用时:848ms
  • 内存:59472kb
  • [2024-11-23 14:05:42]
  • 提交

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...

output:


result: