QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#782865#9786. Magical BagsdaduoliWA 4ms28484kbC++141.4kb2024-11-25 21:54:232024-11-25 21:54:23

Judging History

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

  • [2024-11-25 21:54:23]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:28484kb
  • [2024-11-25 21:54:23]
  • 提交

answer

#include<bits/stdc++.h>
#define Yzl unsigned long long
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
#define lob lower_bound
#define upb upper_bound
#define pb emplace_back
typedef long long LL;

using namespace std;

const Yzl Lty=20120712;

const int MAXN=5e5+10;
int n;
int len[MAXN],tot,lsh[MAXN],L[MAXN],R[MAXN],l[MAXN],r[MAXN];
vector<int> e[MAXN];
struct itv {
	int l,r;
}ind[MAXN]; int cnt,tp;
int main () { 
	scanf("%d",&n); int ans=0;
	for(int i=1;i<=n;++i) {
		scanf("%d",&len[i]); for(int j=1;j<=len[i];++j) { int x; scanf("%d",&x); e[i].pb(x); lsh[++tot]=x; }
	} sort(lsh+1,lsh+1+tot); tot=unique(lsh+1,lsh+1+tot)-lsh-1;
	for(int i=1;i<=n;++i) for(int j=0;j<len[i];++j) e[i][j]=lob(lsh+1,lsh+1+tot,e[i][j])-lsh;
	for(int i=1;i<=n;++i) { if(len[i]==1) { ++ans; continue; }
		sort(e[i].begin(),e[i].end()); ans+=2; 
		l[++tp]=e[i][0]; r[++tp]=e[i][len[i]-1];
	} sort(l+1,l+1+tp); sort(r+1,r+1+tp); r[tp+1]=Lty;
	for(int i=1;i<=n;++i) { if(len[i]==1) continue;
		L[i]=l[lob(l+1,l+1+tp,e[i][len[i]-1])-l-1];
		R[i]=r[upb(r+1,r+1+tp,e[i][0])-r];
		
		bool sf=0;
		for(int j=0;j<len[i];++j) {
			if(e[i][j]<=R[i]&&e[i][j]>=L[i]) sf=1;
		}
		if(sf) ind[++cnt]=(itv){e[i][0],e[i][len[i]-1]};
	} sort(ind+1,ind+1+cnt,[&](itv a,itv b){return a.l<b.l;});
	int lt=0;
	for(int i=1;i<=cnt;++i) {
		if(ind[i].l>lt) lt=ind[i].r,--ans;
		else lt=min(lt,ind[i].r);
	} printf("%d\n",ans);
	return 0;
}

详细

Test #1:

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

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: 3ms
memory: 20288kb

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

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

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

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: -100
Wrong Answer
time: 4ms
memory: 28364kb

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:

172

result:

wrong answer 1st numbers differ - expected: '175', found: '172'