bzoj 4383 [POI2015]Pustynia

bzoj 4383 [POI2015]Pustynia

​​ Description

给定一个长度为n的正整数序列a，每个数都在1到10^9范围内，告诉你其中s个数，并给出m条信息，每条信息包含三个数l,r,k以及接下来k个正整数，表示a[l],a[l+1],…,a[r-1],a[r]里这k个数中的任意一个都比任意一个剩下的r-l+1-k个数大（严格大于，即没有等号）。 请任意构造出一组满足条件的方案，或者判断无解。 Input

第一行包含三个正整数n,s,m(1<=s<=n<=100000，1<=m<=200000)。 接下来s行，每行包含两个正整数p[i],d​​​i​​​，表示已知a[p[i]]=d[i]，保证p[i]递增。 接下来m行，每行一开始为三个正整数l[i],r[i],k​​​i​​​，接下来k[i]个正整数x[1],x[2],…,x​​k[i]​​​，表示这k[i]个数中的任意一个都比任意一个剩下的r[i]-l[i]+1-k[i]个数大。Σk <= 300,000 Output

若无解，则输出NIE。 否则第一行输出TAK，第二行输出n个正整数，依次输出序列a中每个数。 Sample Input 5 2 2 2 7 5 3 1 4 2 2 3 4 5 1 4 Sample Output TAK 6 7 1000000000 6 3 HINT

Source

鸣谢Claris

天天写题3min调试一整年

考虑将区间拆开每个点划分的都是一段区间 那么由于要求我这些点比这些零散的区间都要大 那么不妨新建一个虚点 然后每个点都向那个点连 然后那个点再像区间覆盖一样去覆盖线段树上的点即可 然后拓扑排序

#include#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++; }inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f; }const int N=100100;struct node{ int y,next,z;}data[N*80];struct node1{int left,right;}tree[N<<1];int h[N<<2],cnt,num,n,s,m,root,v[N<<2],dp[N<<2],q[N<<2],pos[N],in[N<<2];inline void insert1(int x,int y,int z){ data[++num].y=y;data[num].next=h[x];h[x]=num;++in[y];data[num].z=z;}inline void build(int &x,int l,int r){ x=++cnt;if (l==r) {pos[l]=x;return;}int mid=l+r>>1; build(tree[x].left,l,mid);build(tree[x].right,mid+1,r); insert1(tree[x].left,x,0);insert1(tree[x].right,x,0);}inline void modify(int x,int l,int r,int l1,int r1){ if (l1>r1) return; if(l1<=l&&r1>=r) {insert1(x,cnt,0);return;}int mid=l+r>>1; if(l1<=mid) modify(tree[x].left,l,mid,l1,r1); if(r1>mid) modify(tree[x].right,mid+1,r,l1,r1);}int main(){ freopen("bzoj4383.in","r",stdin); n=read();s=read();m=read();build(root,1,n); for (int i=1;i<=s;++i) v[pos[read()]]=read(); for (int owo=1;owo<=m;++owo){ ++cnt;int l=read(),r=read(),k=read(),lt=l; for (int i=1;i<=k;++i){ int p=read(); insert1(cnt,pos[p],1); modify(root,1,n,lt,p-1); lt=p+1; }modify(root,1,n,lt,r); }int h1=1,t1=0; //for (int i=1;i<=num;++i) printf("%d %d %d\n",data[i].x,data[i].y,data[i].z); for (int i=1;i<=cnt;++i) if(!in[i]) q[++t1]=i; while(h1<=t1){ int x=q[h1++]; if (!dp[x]) dp[x]=1; if (dp[x]>1e9||dp[x]>v[x]&&v[x]) {puts("NIE");return 0;} if (v[x]) dp[x]=v[x]; for (int i=h[x];i;i=data[i].next){ int y=data[i].y; dp[y]=max(dp[y],dp[x]+data[i].z); if (!--in[y]) q[++t1]=y; } }if (t1!=cnt) {puts("NIE");return 0;}puts("TAK"); for (int i=1;i<=n;++i) printf("%d,dp[pos[i]]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。