QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#773926#9786. Magical Bags新月争霸 (Jiaming Lin, Jingqi Wan, Jun Yin)#RE 2ms12348kbC++141.3kb2024-11-23 10:52:362024-11-23 10:52:40

Judging History

This is the latest submission verdict.

  • [2024-11-23 10:52:40]
  • Judged
  • Verdict: RE
  • Time: 2ms
  • Memory: 12348kb
  • [2024-11-23 10:52:36]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int N=2e5+9;
int n;
vector<int> a[N];
int lsh[N],lm=0;
int l0[N],r0[N];
struct Node{
	int l,r;
	Node(){} Node(int l_,int r_){l=l_,r=r_;}
}b[N];
bool cmp(Node x,Node y){return x.r<=y.r;}
int m=0;
signed main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int siz;
		scanf("%d",&siz);
		for(int j=1;j<=siz;j++)
		{
			int x;
			scanf("%d",&x);
			lsh[++lm]=x;
			a[i].push_back(x);
		}
		sort(a[i].begin(),a[i].end());
	}
	sort(lsh+1,lsh+lm+1);
	lm=unique(lsh+1,lsh+lm+1)-lsh-1;
	for(int i=1;i<=n;i++)
	for(int j=0;j<a[i].size();j++) a[i][j]=lower_bound(lsh+1,lsh+lm+1,a[i][j])-lsh;
	for(int i=1;i<=n;i++) l0[i]=a[i][0],r0[i]=a[i].back();
	
//	for(int i=1;i<=n;i++)
//	{
//		for(int j:a[i]) cerr<<j<<" ";cerr<<endl;
//	}
	
	sort(l0+1,l0+n+1);
	sort(r0+1,r0+n+1);
	for(int i=1;i<=n;i++)
	{
		int rr=*lower_bound(r0+1,r0+n+1,a[i][0]);
		int ll=*(upper_bound(l0+1,l0+n+1,a[i].back())-1);
//		cerr<<a[i][0]<<" "<<a[i].back()<<endl;
//		cerr<<i<<" : "<<ll<<" "<<rr<<endl;
		bool pd=0;
		for(int p:a[i]) if(ll<=p&&p<=rr) {pd=1;break;}
		if(pd) b[++m]=Node(a[i][0],a[i].back());
	}
	int ans=n*2;
	sort(b+1,b+m+1,cmp);
	int lstr=0;
	for(int i=1;i<=m;i++) if(b[i].l>lstr) ans--,lstr=b[i].r;
	printf("%d\n",ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9348kb

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: 9260kb

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: 11476kb

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: 2ms
memory: 11528kb

input:

4
1 1
1 2
1 3
1 4

output:

4

result:

ok 1 number(s): "4"

Test #5:

score: 0
Accepted
time: 0ms
memory: 11992kb

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: 2ms
memory: 12348kb

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: 2ms
memory: 11612kb

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: 1ms
memory: 8664kb

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: 11708kb

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: 1ms
memory: 8744kb

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: 1ms
memory: 8692kb

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: 11916kb

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: 2ms
memory: 9356kb

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: 2ms
memory: 8964kb

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: -100
Runtime Error

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:


result: