寒假来了，又到了小明和女神们约会的季节。
小明虽为***丝级码农，但非常活跃，女神们常常在小明网上的大段发言后热情回复“呵呵”，所以，小明的最爱就是和女神们约会。与此同时，也有很多基友找他开黑，由于数量实在过于巨大，怎么安排时间便成了小明的一大心事。
我们已知小明一共有T的空闲时间，期间会有很多女神或者基友来找小明。
作为一个操作系统曾经怒考71分的大神，小明想到了一个算法，即“首次适应算法”，根据操作系统课本的描述，就是找一段最靠前的符合要求的连续空间分配给每个请求，由此小明做出了一个决定：
当一个基友来找小明时，小明就根据“首次适应算法”来找一段空闲的时间来和基友约好，如果找到，就说“X,let’s fly”（此处，X为开始时间），否则就说“fly with yourself”；
当女神来找小明时，先使用一次“首次适应算法”，如果没有找到，小明就冒着木叽叽的风险无视所有***丝基友的约定，再次使用“无视基友首次适应算法”，两次只要有一次找到，就说“X,don’t put my gezi”（此处，X为开始时间），否则就说“wait for me”
当然，我们知道小明不是一个节操负无穷的人，如果和女神约会完，还有剩余时间，他还是会和原来约好的基友去dota的。（举个例子：小西（***丝）和小明约好在1~5这个时间单位段内打dota，这时候，女神来和小明预约长度为3的时间段，那么最终就是1~3小明去和女神约会，搞定后在4~5和小西打dota）
小明偶尔也会想要学习新知识，此时小明就会把某一个时间区间的所有已经预定的时间全部清空用来学习并且怒吼“I am the hope of chinese chengxuyuan!!”，不过小明一般都是三分钟热度，再有人来预定的话，小明就会按耐不住寂寞把学习新知识的时间分配出去。
Input
输入第一行为CASE，表示有CASE组测试数据；
每组数据以两个整数T，N开始，T代表总共的时间，N表示预约请求的个数；
接着的N行，每行表示一个女神或者基友的预约，“NS QT”代表一个女神来找小明约一段长为QT的时间，“DS QT”则代表一个***丝的长为QT的请求，当然也有可能是小明想学知识了，“STUDY!! L R”代表清空L~R区间内的所有请求。
[Technical Specification]
1. 1 <= CASE <= 30
2. 1 <= T, N <= 100000
3. 1 <= QT <= 110000
4. 1 <= L <= R <=T
Output
对于每一个case，第一行先输出“Case C:”代表是第几个case，然后N行，每行对应一个请求的结果(参照描述)。
输出样本(可复制此处)：
“X,let's fly”,”fly with yourself”,”X,don't put my gezi”,”wait for me”,”I am the hope of chinese chengxuyuan!!”
Sample Input
1 5 6 DS 3 NS 2 NS 4 STUDY!! 1 5 DS 4 NS 2
Sample Output
Case 1: 1,let's fly 4,don't put my gezi wait for me I am the hope of chinese chengxuyuan!! 1,let's fly 1,don't put my gezi
C++版本一
#include<bits\stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+7;
int ll[maxn<<2],rr[maxn<<2],mm[maxn<<2];
int ill[maxn<<2],irr[maxn<<2],imm[maxn<<2];
void build(int rt,int l,int r)
{
ll[rt]=rr[rt]=mm[rt]=r-l+1;
ill[rt]=irr[rt]=imm[rt]=r-l+1;
if(l==r) return ;
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
}
void push_up(int rt,int l,int r)
{
int mid=(r+l)>>1;
mm[rt]=max(mm[rt<<1],mm[rt<<1|1]);
mm[rt]=max(mm[rt],rr[rt<<1]+ll[rt<<1|1]);
ll[rt]=ll[rt<<1];
rr[rt]=rr[rt<<1|1];
if(ll[rt]==mid-l+1) ll[rt]+=ll[rt<<1|1];
if(rr[rt]==r-mid) rr[rt]+=rr[rt<<1];
imm[rt]=max(imm[rt<<1],imm[rt<<1|1]);
imm[rt]=max(imm[rt],irr[rt<<1]+ill[rt<<1|1]);
ill[rt]=ill[rt<<1];
irr[rt]=irr[rt<<1|1];
if(ill[rt]==mid-l+1) ill[rt]+=ill[rt<<1|1];
if(irr[rt]==r-mid) irr[rt]+=irr[rt<<1];
}
void push_down(int rt,int l,int r)
{
int mid=(l+r)>>1;
if(mm[rt]==r-l+1)
{
ll[rt<<1]=rr[rt<<1]=mm[rt<<1]=mid-l+1;
ll[rt<<1|1]=rr[rt<<1|1]=mm[rt<<1|1]=r-mid;
}
else if(mm[rt]==0)
{
ll[rt<<1]=rr[rt<<1]=mm[rt<<1]=0;
ll[rt<<1|1]=rr[rt<<1|1]=mm[rt<<1|1]=0;
}
if(imm[rt]==r-l+1)
{
ill[rt<<1]=irr[rt<<1]=imm[rt<<1]=mid-l+1;
ill[rt<<1|1]=irr[rt<<1|1]=imm[rt<<1|1]=r-mid;
}
else if(imm[rt]==0)
{
ill[rt<<1]=irr[rt<<1]=imm[rt<<1]=0;
ill[rt<<1|1]=irr[rt<<1|1]=imm[rt<<1|1]=0;
}
}
// 0---DS 1---NS 2---STUDY
void update(int rt,int l,int r,int ul,int ur,int flag)
{
if(ul<=l&&ur>=r)
{
if(flag==1)
ll[rt]=rr[rt]=mm[rt]=ill[rt]=irr[rt]=imm[rt]=0;
else if(flag==0)
ll[rt]=rr[rt]=mm[rt]=0;
else
ll[rt]=rr[rt]=mm[rt]=ill[rt]=irr[rt]=imm[rt]=r-l+1;
return ;
}
push_down(rt,l,r);
int mid=(l+r)>>1;
if(ul<=mid) update(rt<<1,l,mid,ul,ur,flag);
if(ur>mid) update(rt<<1|1,mid+1,r,ul,ur,flag);
push_up(rt,l,r);
}
// find the left end of a corresponding interval
// 0---DS 1---NS
int query(int rt,int l,int r,int dur,int flag)
{
if(l==r) return l;
int mid=(l+r)>>1;
push_down(rt,l,r);
if(flag)
{
if(imm[rt<<1]>=dur) return query(rt<<1,l,mid,dur,flag);
else if(irr[rt<<1]+ill[rt<<1|1]>=dur) return mid-irr[rt<<1]+1;
else return query(rt<<1|1,mid+1,r,dur,flag);
}
else
{
if(mm[rt<<1]>=dur) return query(rt<<1,l,mid,dur,flag);
else if(rr[rt<<1]+ll[rt<<1|1]>=dur) return mid-rr[rt<<1]+1;
else return query(rt<<1|1,mid+1,r,dur,flag);
}
}
char option[10];
int main()
{
/************
freopen("in.txt","r",stdin);
freopen("out1.txt","w",stdout);
/********************/
int T,kase=0;
int t,n,dur;
scanf("%d",&T);
while(++kase<=T)
{
scanf("%d%d",&t,&n);
printf("Case %d:\n",kase);
build(1,1,t);
for(int i=0;i<n;i++)
{
scanf("%s",option);
if(option[0]=='D')
{
scanf("%d",&dur);
if(mm[1]<dur) puts("fly with yourself");
else
{
int res=query(1,1,t,dur,0);
printf("%d,let's fly\n",res);
update(1,1,t,res,res+dur-1,0);
}
}
else if(option[0]=='N')
{
scanf("%d",&dur);
if(mm[1]>=dur)
{
int res=query(1,1,t,dur,0);
printf("%d,don't put my gezi\n",res);
update(1,1,t,res,res+dur-1,1);
}
else if(imm[1]>=dur)
{
int res=query(1,1,t,dur,1);
printf("%d,don't put my gezi\n",res);
update(1,1,t,res,res+dur-1,1);
}
else
puts("wait for me");
}
else
{
int l,r;
scanf("%d%d",&l,&r);
update(1,1,t,l,r,2);
puts("I am the hope of chinese chengxuyuan!!");
}
}
}
return 0;
}
C版本二
WA
鬼知道问题在哪
仿照版本一
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
const int N=100000+100;
int t,n,mm;
struct node{
int dl,dr;
int nl,nr;
int dsum;
int nsum;
}tree[N<<2];
void DPushup(int i,int l,int r){
int m=(r+l)>>1;
tree[i].dsum=max(tree[i<<1].dsum,tree[i<<1|1].dsum);
tree[i].dsum=max(tree[i].dsum,tree[i<<1].dr+tree[i<<1|1].dl);
tree[i].dl=tree[i<<1].dl;
tree[i].dr=tree[i<<1|1].dr;
if(tree[i].dl==m-l+1) tree[i].dl+=tree[i<<1|1].dl;
if(tree[i].dr==r-m) tree[i].dr+=tree[i<<1].dr;
}
void NPushup(int i,int l,int r){
int m=(r+l)>>1;
tree[i].nsum=max(tree[i<<1].nsum,tree[i<<1|1].nsum);
tree[i].nsum=max(tree[i].nsum,tree[i<<1].nr+tree[i<<1|1].nl);
tree[i].nl=tree[i<<1].nl;
tree[i].nr=tree[i<<1|1].nr;
if(tree[i].nl==m-l+1) tree[i].nl+=tree[i<<1|1].nl;
if(tree[i].nr==r-m) tree[i].nr+=tree[i<<1].nr;
}
void DPushdown(int i,int l,int r){
int m=(l+r)>>1;
if(tree[i].dsum==r-l+1)
{
tree[i<<1].dsum=tree[i<<1].dl=tree[i<<1].dr=m-l+1;
tree[i<<1|1].dsum=tree[i<<1|1].dl=tree[i<<1|1].dr=r-m;
}
else if(tree[i].dsum==0)
{
tree[i<<1].dsum=tree[i<<1].dl=tree[i<<1].dr=0;
tree[i<<1|1].dsum=tree[i<<1|1].dl=tree[i<<1|1].dr=0;
}
}
void NPushdown(int i,int l,int r){
int m=(l+r)>>1;
if(tree[i].nsum==r-l+1)
{
tree[i<<1].nsum=tree[i<<1].nl=tree[i<<1].nr=m-l+1;
tree[i<<1|1].nsum=tree[i<<1|1].nl=tree[i<<1|1].nr=r-m;
}
else if(tree[i].nsum==0)
{
tree[i<<1].nsum=tree[i<<1].nl=tree[i<<1].nr=0;
tree[i<<1|1].nsum=tree[i<<1|1].nl=tree[i<<1|1].nr=0;
}
}
void Build(int i,int l,int r){
tree[i].dl=tree[i].dr=tree[i].dsum=r-l+1;
tree[i].nl=tree[i].nr=tree[i].nsum=r-l+1;
if(l!=r){
int m=(l+r)>>1;
Build(i<<1,l,m);
Build(i<<1|1,m+1,r);
}
}
int DQuery(int i,int l,int r,int L ){
if(l==r){
return l;
}
int m=(l+r)>>1;
DPushdown(i,l,r);
if(tree[i<<1].dsum>=L)
return DQuery(i<<1,l,m,L);
else if(tree[i<<1].dr+tree[i<<1|1].dl>=L)
return m-tree[i<<1].dr+1;
else
return DQuery(i<<1|1,m+1,r,L);
}
int NQuery(int i,int l,int r,int L){
if(l==r){
return l;
}
int m=(l+r)>>1;
NPushdown(i,l,r);
if(tree[i<<1].nsum>=L)
return NQuery(i<<1,l,m,L);
else if(tree[i<<1].nr+tree[i<<1|1].nl>=L)
return m-tree[i<<1].nr+1;
else
return NQuery(i<<1|1,m+1,r,L);
}
void DUpdata(int i,int l,int r,int L,int R){
if(L<=l&&r<=R){
tree[i].dsum=tree[i].dl=tree[i].dr=0;
return;
}
DPushdown(i,l,r);
int m=(l+r)>>1;
if(L<=m)DUpdata(i<<1,l,m,L,R);
if(m<R)DUpdata(i<<1|1,m+1,r,L,R);
DPushup(i,l,r);
}
void NUpdata(int i,int l,int r,int L,int R){
if(L<=l&&r<=R){
tree[i].nsum=tree[i].nl=tree[i].nr=tree[i].dsum=tree[i].dl=tree[i].dr=0;
return;
}
NPushdown(i,l,r);
DPushdown(i,l,r);
int m=(l+r)>>1;
if(L<=m)NUpdata(i<<1,l,m,L,R);
if(m<R)NUpdata(i<<1|1,m+1,r,L,R);
NPushup(i,l,r);
DPushup(i,l,r);
}
void SUpdata(int i,int l,int r,int L,int R){
if(L<=l&&r<=R){
tree[i].dsum=tree[i].dl=tree[i].dr=tree[i].nsum=tree[i].nl=tree[i].nr=r-l+1;
return;
}
NPushdown(i,l,r);
DPushdown(i,l,r);
int m=(l+r)>>1;
if(L<=m)SUpdata(i<<1,l,m,L,R);
if(m<R)SUpdata(i<<1|1,m+1,r,L,R);
NPushup(i,l,r);
DPushup(i,l,r);
}
int main()
{
scanf("%d",&t);
for(int T=1;T<=t;T++){
printf("Case %d:\n",T);
scanf("%d%d",&n,&mm);
char c[10];
int q,x,y;
Build(1,1,n);
while(mm--){
scanf("%s",c);
if(c[0]=='D'){
scanf("%d",&q);
if(tree[1].dsum>=q){
int a=DQuery(1,1,n,q);
cout <<a<< ",let’s fly" << endl;
DUpdata(1,1,n,a,a+q-1);
}else
cout << "fly with yourself" << endl;
}else if(c[0]=='N'){
scanf("%d",&q);
if(tree[1].dsum>=q){
int a=DQuery(1,1,n,q);
NUpdata(1,1,n,a,a+q-1);
cout <<a<< ",don’t put my gezi" << endl;
}else if(tree[1].nsum>=q){
int a=NQuery(1,1,n,q);
NUpdata(1,1,n,a,a+q-1);
cout <<a<< ",don’t put my gezi" << endl;
}else
cout << "wait for me" << endl;
}else{
scanf("%d%d",&x,&y);
SUpdata(1,1,n,x,y);
cout << "I am the hope of chinese chengxuyuan!!" << endl;
}
}
}
//cout << "Hello world!" << endl;
return 0;
}
京公网安备 11010502036488号