欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Gym - 100886I 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest I - Archaeological Res

程序员文章站 2022-05-22 10:50:07
...

假如第i行有数j,说明i+1到j-1的数均与j不同
那么从前往后依次确定每个数,结合上述限制贪心即可

#include<bits/stdc++.h>
using namespace std;
#define M 524288
#define N 300005

int ans,aim,n,a[N],t[M<<1],vis[N];

void find(int k,int l,int r)
{
	if (l==r){ans=l;return;}
	int mid=l+r>>1;
	if (t[k<<1]<aim) return find(k<<1,l,mid);
	find(k<<1|1,mid+1,r);
}

void ins(int k,int l,int r)
{
	if (l==r){t[k]=aim;return;}
	int mid=l+r>>1;
	if (ans<=mid) ins(k<<1,l,mid);
	else ins(k<<1|1,mid+1,r);
	t[k]=min(t[k<<1],t[k<<1|1]);
}

int main()
{
	scanf("%d",&n);
	for (int i=1,c;i<=n;i++)
	{
		scanf("%d",&c);
		for (int k;c--;)
		{
			scanf("%d",&k);
			if (!vis[k]) vis[k]=i;
		}
	}
	for (int i=1;i<=n;i++)
	{
		if (!vis[i]) ans=1;
		else aim=vis[i]+1,find(1,1,M);
		a[i]=ans;aim=i;
		ins(1,1,M);
	}
	for (int i=1;i<=n;i++) printf("%d%c",a[i],i==n?'\n':' ');
}