QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#773996#9786. Magical Bagsucup-team3510#WA 1ms7680kbC++201.6kb2024-11-23 11:11:152024-11-23 11:11:16

Judging History

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

  • [2024-11-23 11:11:16]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7680kb
  • [2024-11-23 11:11:15]
  • 提交

answer

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
int n,ans=0,l[200010],r[200010],A[200010];
vector<int> a[200010],v;
inline bool cmp(const vector<int> &x,
const vector<int> &y)
{
	return x.back()<y.back();
}
int f[200010];
inline void add(int x,int y)
{
	for(;x<=n;f[x]=max(f[x],y),x+=x&-x);
}
inline int query(int x)
{
	int ret=0;
	for(;x;ret=max(ret,f[x]),x&=x-1);
	return ret;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1,x;i<=n;i++)
	{
		cin>>x;
		a[i].resize(x);
		for(int j=0;j<x;j++)
		{
			cin>>a[i][j];
			v.emplace_back(a[i][j]);
		}
		sort(a[i].begin(),a[i].end());
		ans+=min(2,x);
	}
	sort(v.begin(),v.end());
	int num=unique(v.begin(),v.end())-v.begin();
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<a[i].size();j++)
		{
			a[i][j]=lower_bound(v.begin(),
			v.begin()+num,a[i][j])-v.begin()+1;
		}
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		int L=a[i][0];
		int R=A[i]=a[i].back();
		add(R,L);
		if(a[i].size()==1)
		{
			continue;
		}
		l[i]=query(num-L);
		r[i]=A[lower_bound(A+1,A+i+1,L)-A];
	}
	set<int> s;
	for(int i=n;i;i--)
	{
		if(a[i].size()==1)
		{
			continue;
		}
		s.insert(-a[i][0]);
		auto it=s.lower_bound(-a[i][1]);
		l[i]=max(l[i],-(*it));
	}
	for(int i=1,last=0;i<=n;i++)
	{
		if(a[i].size()==1||l[i]>r[i])
		{
			continue;
		}
		if(last<a[i][0])
		{
			int p=lower_bound(a[i].begin(),
			a[i].end(),l[i])-a[i].begin();
			if(p==a[i].size()||a[i][p]>r[i])
			{
				continue;
			}
			last=a[i].back();
			ans--;
		}
	}
	cout<<ans<<endl;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5676kb

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: 0ms
memory: 5592kb

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

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

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

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:

171

result:

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