QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#774847#9786. Magical Bagsucup-team1004#WA 2ms12144kbC++141.2kb2024-11-23 14:00:382024-11-23 14:00:39

Judging History

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

  • [2024-11-23 14:00:39]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:12144kb
  • [2024-11-23 14:00:38]
  • 提交

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;
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]);
	}
	for(int i=1;i<=n;i++)
	{
		if((int)v[i].size()==1) continue;
		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]};
	}
	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: 2ms
memory: 12084kb

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

input:

4
1 1
1 2
1 3
1 4

output:

4

result:

ok 1 number(s): "4"

Test #3:

score: 0
Accepted
time: 2ms
memory: 11960kb

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

input:

4
1 1
1 2
1 3
1 4

output:

4

result:

ok 1 number(s): "4"

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 12104kb

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:

179

result:

wrong answer 1st numbers differ - expected: '177', found: '179'