约会安排[HDU - 4553] T6 D24

约会安排[HDU - 4553]( Problem - 4553 (hdu.edu.cn) ) T6 D24

思路:

线段树区间合并。线段树维护NS和DS的左连续区间和右连续区间,更新时按优先级顺序更新,学习>NS>DS

/*
               #########                       
              ############                     
              #############                    
             ##  ###########                   
            ###  ###### #####                  
            ### #######   ####                 
           ###  ########## ####                
          ####  ########### ####               
        #####   ###########  #####             
       ######   ### ########   #####           
       #####   ###   ########   ######         
      ######   ###  ###########   ######       
     ######   #### ##############  ######      
    #######  ##################### #######     
    #######  ##############################    
   #######  ###### ################# #######   
   #######  ###### ###### #########   ######   
   #######    ##  ######   ######     ######   
   #######        ######    #####     #####    
    ######        #####     #####     ####     
     #####        ####      #####     ###      
      #####      ;###        ###      #        
        ##       ####        ####     

HDU - 4553 真折磨啊         
*/
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<string.h>
#define ll long long 
#define ls (p<<1)
#define rs ((p<<1)|1)
#define mid ((t[p].l+t[p].r)>>1) 
using namespace std;
int read(){int x=0,f=1;char ch=getchar();while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(int x){if(x < 0){putchar(‘-‘);x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + ‘0‘);}
const int qs=2e5+7;
struct Tree{
	int l,r,dl,dr,nl,nr,dsum,nsum,add,ann;
	#define l(x) t[x].l
	#define r(x) t[x].r
	#define dl(x) t[x].dl
	#define dr(x) t[x].dr
	#define nl(x) t[x].nl
	#define nr(x) t[x].nr
	#define dsum(x) t[x].dsum
	#define nsum(x) t[x].nsum
	#define add(x) t[x].add
	#define ann(x) t[x].ann
}t[qs<<2];
void pushup(int p){
	dl(p)=dl(ls)+(dl(ls)==r(ls)-l(ls)+1 ? dl(rs) : 0);
	dr(p)=dr(rs)+(dr(rs)==r(rs)-l(rs)+1 ? dr(ls) : 0);
	dsum(p)=max(max(dsum(ls),dsum(rs)),dr(ls)+dl(rs));
	nl(p)=nl(ls)+(nl(ls)==r(ls)-l(ls)+1 ? nl(rs) : 0);
	nr(p)=nr(rs)+(nr(rs)==r(rs)-l(rs)+1 ? nr(ls) : 0);
	nsum(p)=max(max(nsum(ls),nsum(rs)),nr(ls)+nl(rs));
}
void build(int p,int l,int r){
	l(p)=l,r(p)=r;
	add(p)=ann(p)=-1;
	if(l==r) {
		dl(p)=dr(p)=dsum(p)=1;
		nl(p)=nr(p)=nsum(p)=1;
		return;
	}
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(p);
}
void down(int p){
	if(add(p)!=-1){
		dl(ls)=dr(ls)=dsum(ls)=(r(ls)-l(ls)+1)*add(p);
		dl(rs)=dr(rs)=dsum(rs)=(r(rs)-l(rs)+1)*add(p);
		add(ls)=add(rs)=add(p);
	}
	
	if(ann(p)!=-1){
		nl(ls)=nr(ls)=nsum(ls)=(r(ls)-l(ls)+1)*ann(p);
		nl(rs)=nr(rs)=nsum(rs)=(r(rs)-l(rs)+1)*ann(p);
		ann(ls)=ann(rs)=ann(p);
	}
	add(p)=ann(p)=-1;
}
void update(int p,int l,int r,int k,int nk){
	down(p);	
	if(l<=l(p)&&r>=r(p)){
		dl(p)=dr(p)=dsum(p)=(r(p)-l(p)+1)*k;
		if(nk!=-1) nl(p)=nr(p)=nsum(p)=(r(p)-l(p)+1)*nk;
		add(p)=k;
		ann(p)=nk;
			return;
	}	
	if(l<=mid) update(ls,l,r,k,nk);
	if(r>mid) update(rs,l,r,k,nk);
	pushup(p);
}
int ask(int p,int len,int k){
	down(p);
	if(l(p)==r(p)) return 1;
	if(k==1){
		if(dsum(ls)>=len) return ask(ls,len,k);
		else if(dl(rs)+dr(ls)>=len) return mid-dr(ls)+1;
		else return ask(rs,len,k);
	}
	else{
		if(nsum(ls)>=len) return ask(ls,len,k);
		else if(nl(rs)+nr(ls)>=len) return mid-nr(ls)+1;
		else return ask(rs,len,k);
	}
	return 0;
} 
int T,n,q;
int main(){
	T=read();
	for(int ti=1;ti<=T;++ti){
	printf("Case %d:\n",ti);
	n=read(),q=read();
	build(1,1,n);
	while(q--){
		string s;
		int l,len,r;
		cin>>s;
		if(s=="DS"){
			len=read();
			if(dsum(1)<len){
				printf("fly with yourself\n");
				continue;
			}
			int ans=ask(1,len,1);
			printf("%d,let‘s fly\n",ans);
			update(1,ans,ans+len-1,0,-1);
		}
		else if(s=="NS"){
			len=read();
			if(dsum(1)<len){
				if(nsum(1)<len){
					printf("wait for me\n");
					continue;
				}
				int ans=ask(1,len,2);
				printf("%d,don‘t put my gezi\n",ans);
				update(1,ans,ans+len-1,0,0);
				continue;
			}
			int ans=ask(1,len,1);
			printf("%d,don‘t put my gezi\n",ans);
			update(1,ans,ans+len-1,0,0);
		}
		else{
			l=read(),r=read();
			update(1,l,r,1,1);
			printf("I am the hope of chinese chengxuyuan!!\n");
		}
	}
}	
	return 0;
}

约会安排[HDU - 4553] T6 D24

上一篇:075.程序的内存模型-new运算符


下一篇:fabric根据Txid查询交易信息