[SCOI2009]生日礼物

Time Limit:10000MS  Memory Limit:165536K
Total Submit:42 Accepted:22
Case Time Limit:1000MS

Description

小西有一条很长的彩带，彩带上挂着各式各样的彩珠。已知彩珠有N个，分为K种。简单的说，可以将彩带考虑为x轴，每一个彩珠有一个对应的坐标(即 位置)。某些坐标上可以没有彩珠，但多个彩珠也可以出现在同一个位置上。
小布生日快到了，于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮，小西希望这一段彩带中能包含所有种类的彩珠。同时，为了方便，小西希 望这段彩带尽可能短，你能帮助小西计算这个最短的长度么？彩带的长度即为彩带开始位置到结束位置的位置差。

Input

第一行包含两个整数N, K，分别表示彩珠的总数以及种类数。接下来K行，每行第一个数为Ti，表示第i种彩珠的数目。接下来按升序给出Ti个非负整数，为这Ti个彩珠分别出现的 位置。

Output

应包含一行，为最短彩带长度。

Sample Input

6 3
1 5
2 1 7
3 1 3 8

Sample Output

3

Hint

有多种方案可选，其中比较短的是1~5和5~8。后者长度为3最短。
【数据规模】
对于50%的数据， N≤10000；
对于80%的数据， N≤800000；
对于100%的数据，1≤N≤1000000，1≤K≤60，0≤彩珠位置<2^31。

Source

61.187.179.132:8080/JudgeOnline/showproblem
额。。算法是很好想的，就是从小到大枚举每个位置，然后找出每种颜色在它后面的第一个然后取其中最大的那个更新答案。。我早上就想出来了囧。。
一开始我想的算法是NK的。。超的很厉害囧。。
后来我想用一个set来保存所有颜色大于当前位置的最小位置，然后运用set的找最大值和最小值操作，就很方便了。每次看set中的最小值是不是小于当前位置，是的话后移这个值。就是NLogK了。。可惜极限数据要1.6S。还是超时。。
我又优化了一下还是超时，没办法只好先放着了。。
现在突然发现由于最大值肯定是递增的，所以插入的时候更新一下就OK了。真正只需要知道最小值，那么用一个heap就可以了。。为了方便编程我用了priority_queue
Code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<ctime>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=1000000,maxk=60;
typedef vector<int> vi;
typedef vi::iterator it;
vi A,S[maxk];
int n,k;
void Init()
{
cin>>n>>k;A.resize(n);it nowA=A.begin();
rep(i,k)
{
int t,x;scanf("%d",&t);S[i].resize(t+1);it nowS=S[i].begin();
rep(j,t)scanf("%d",&x),(*nowA++)=(*nowS++)=x;
*nowS++=inf;
}
}
struct cmp
{
bool operator()(const it&a,const it&b)const
{return *a>*b;}
};
void Work()
{
int s=clock();
sort(all(A));
int ans=inf,Max=0;
priority_queue<it,vector<it>,cmp> Q;
rep(i,k)Q.push(S[i].begin()),Max=max(Max,*S[i].begin());
rep(i,n)
{
int t=A[i];
while(*Q.top()<t)
{
it j=Q.top();Q.pop();
Max=max(Max,*++j);
if(Max==inf)break;
Q.push(j);
}
if(Max==inf)break;
ans=min(ans,Max-t);
}
cout<<ans<<endl;
}
int main()
{
//freopen("in","r",stdin);
int s=clock();
Init();
Work();
}