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':' ');
}
上一篇: Petrozavodsk Winter Training Camp 2018: Carnegie Mellon U Contest A. Mines
下一篇: codeforces 825B(DFS)
推荐阅读
-
[Gym] - 100886K 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest K - Toll Roads
-
Gym - 100886I 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest I - Archaeological Res
-
Gym - 100886B 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest B - Game on Bipartite
-
2015-2016 Petrozavodsk Winter Training Camp, Moscow SU Trinity Contest(Gym 100962)
-
Gym - 100886F 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest F - Empty Vessels
-
题解:2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest