bzoj5132 [CodePlus2017年12月]火锅盛宴

bzoj5132 [CodePlus2017年12月]火锅盛宴

​​ 题目背景

SkyDec和YJQQQAQ都是Yazid的好朋友。他们都非常喜欢吃火锅。有一天，他们聚在一起，享受一场火锅盛宴。 题目描述

在这场火锅盛宴中，有一个麻辣浓汤锅底的火锅和n种食物，每种食物数量都是无限的。我们用 11

1 至 nn

n 将这些食材编号。

每种食物煮熟所需要的时间不同，第 ii

i 种食物煮熟需要 sis_i

si​ 单位时间。这表示如果你在第 TT

T 个时刻将一个食物 ii

i 下到火锅里，那么它会在第 T+siT+s_i

T+si 个时刻被煮熟，并且此后一直会延续被煮熟的状态，直到它被拿走为止。

Yazid和YJQQQAQ的口味不同：YJQQQAQ觉得所有食物的好吃程度都是相同的；而Yazid则觉得没有两种食材的好吃程度是相同的，并且，巧合的是，编号越小的食物Yazid越喜欢吃。可怜的SkyDec由于不能吃辣，所以只能帮Yazid和YJQQQAQ煮食物。

整个火锅盛宴持续 10910^9

109 单位时间。在整个盛宴中，三位好朋友除了谈笑风生之外，最重要的事当然就是吃东西了。在任意整数时刻，都有可能发生下列4种事件中的任意一种，我们用 00

0 至 33

3 之间的整数 opop

op 描述事件类型：

0 id：表示SkyDec往火锅里下了一个编号为 idid

id 的食物。

1：Yazid在锅内搜寻熟了的且最喜欢吃的食物，并拿走一个这种食物。特别地，如果锅里没有熟了的食物，那么Yazid会很愤怒。

2 id：YJQQQAQ在锅内搜寻编号为 idid

id 的食物：如果锅里不存在该种食物，则YJQQQAQ会很愤怒；如果锅里存在熟了的该食物，则YJQQQAQ会取走一个并食用；如果锅里只有未煮熟的该种食物，那么YJQQQAQ会希望知道最接近煮熟的该种食物（即锅内存在时间最长的该种食物）还需要多少时间被煮熟。

3 l r:馋涎欲滴的SkyDec想知道，锅里编号在 [l,r][l,r]

[l,r] 之间的且熟了的食物总共有多少个。 输入输出格式

输入格式： 从标准输入读入数据。

本题包含多组数据，输入的第一行为一个正整数 TT

T ，表示数据组数。接下来依次描述每组数据，对于每组数据：

第一行一个正整数 nn

n ，表示食物的种类数。

第二行 nn

n 个用空格隔开的正整数 s1,s2,……sns_1,s_2,……s_n

s1,s2,……sn ，描述每种食物煮熟需要的时间。

第三行一个正整数 QQ

Q ，表示事件的数目。

接下来 QQ

Q 行，每行若干个用空格隔开的非负整数，描述一个事件。先是两个整数 t,opt,op

t,op ，分别表示发生事件的时间以及事件的类型。如果 op=0op=0

op=0 或 op=2op=2

op=2 ，则接下来 11

1 个正整数 idid

id ，意义见题目描述；如果 op=1op=1

op=1 ，则接下来没有其他数；如果 op=3op=3

op=3 ，则接下来 22

2 个正整数 l,rl,r

l,r ，意义见题目描述。

我们保证 tt

t 按输入顺序严格递增。

我们保证 1≤t≤1091\leq t\leq 10^9

1≤t≤109 ， 0≤op≤30\leq op\leq 3

0≤op≤3 ， 1≤id≤n1\leq id\leq n

1≤id≤n ， 1≤l≤r≤n1\leq l\leq r\leq n

1≤l≤r≤n 。

输出格式： 对于每个 op≠0op\neq 0

op≠0 的操作，输出一行表示答案。对于不同的 opop

op ，需要输出的内容如下：

对于 op=1op=1

op=1 ，如果Yazid成功取走食物，则输出他取走食物的编号；否则输出”Yazid is angry.”（不含引号，下同）。

对于 op=2op=2

op=2 ，如果YJQQQAQ成功取走食物，则输出”Succeeded!”；否则，如果锅里有未煮熟的该类食物，输出最接近煮熟的该种食物还需要多少时间被煮熟；否则，输出”YJQQQAQ is angry.”。

对于 op=3op=3

op=3 ，输出锅内编号在指定范围内的熟食的数量。

输出到标准输出。 输入输出样例

输入样例#1： 复制

1 2 1 100 10 1 0 2 2 0 1 3 2 1 4 2 2 5 2 1 200 0 1 201 3 1 2 202 1 203 1 204 1

输出样例#1： 复制

Succeeded! 97 YJQQQAQ is angry. 2 1 2 Yazid is angry.

说明

对于所有数据，保证 T≤4T\leq 4

T≤4 ，保证 n≤100,000n\leq 100,000

n≤100,000 ， Q≤500,000Q\leq 500,000

Q≤500,000 ， 1≤si≤1081\leq s_i\leq 10^8

1≤si≤108 。

来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit：idea/王聿中 命题/王聿中 验题/吕时清，杨景钦

Git Repo：​​leoly说可以啊你写写看 还好我在飞机上又认真想了想发现可以用priority_queue搞定一棵 但还是差点险些tle xx

我首先询问的时候将每个东西煮熟的时间算好 放入优先队列 这时自动按照时间排序 然后每次询问我首先先将煮好的东西提取出来 插入splay中 在splay中我们按照这个下标排序 剩下我们要做的就是模拟他的操作 如果这个东西还没熟 我选择开一个vector来记录 一开始开deque 内存炸了 vector虽然不会自动回收内存 但是他可以将内存自动回收到stl中以便再次利用 还是挺高效方便的 注意需要清空priority_queue&我的vector 针对这个splay我每次需要求一个前驱后驱 什么的 常数就挺大的

#include#include#include#include#include#define N 550000using 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(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=gc();} while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x*f;}int fa[N],val[N],c[N][2],v[N],size[N],cnt,root,n,s[N];struct node1{ int t,id; inline friend bool operator <(const node1 &a,const node1 &b){ return a.t>b.t; }};inline void update(int x){ size[x]=size[c[x][0]]+size[c[x][1]]+v[x];}inline void rotate(int x,int &tar){ int y=fa[x],z=fa[y]; if (y==tar) tar=x;else c[z][c[z][1]==y]=x; int l=c[y][1]==x,r=l^1; fa[c[x][r]]=y;fa[y]=x;fa[x]=z; c[y][l]=c[x][r];c[x][r]=y;update(y);update(x); }inline void splay(int x,int &tar){ while(x!=tar){ int y=fa[x],z=fa[y]; if (y!=tar) {if (c[y][0]==x^c[z][0]==y) rotate(x,tar);else rotate(y,tar);} rotate(x,tar); }}inline void insert1(int &x,int p,int f){ if (!x) {x=++cnt;size[x]=v[x]=1;fa[x]=f;val[x]=p;splay(x,root);return;} if (p==val[x]) {++v[x];++size[x];splay(x,root);return;} if (pp) su=x,succ(c[x][0],p);else succ(c[x][1],p);}inline void print(int x){ if (c[x][0]) print(c[x][0]); printf("%d %d %d\n",val[x],size[x],v[x]); if (c[x][1]) print(c[x][1]);}vector a[N];int main(){// freopen("4032.in","r",stdin);// freopen("4032.out","w",stdout); int T=read(); while(T--){ n=read();for (int i=1;i<=n;++i) s[i]=read();int Q=read();cnt=0; memset(c,0,sizeof(c));root=0;insert1(root,0,root);insert1(root,n+1,root); priority_queue >q; for (int i=1;i<=n;++i) while (a[i].size()) a[i].erase(a[i].begin()); while(Q--){ int t=read(),op=read(); if (!op){ int id=read();node1 tmp;tmp.id=id;tmp.t=t+s[id];q.push(tmp); a[id].push_back(tmp); } if (op==1){ node1 tmp; while(!q.empty()&&q.top().t<=t) { tmp=q.top();q.pop(); insert1(root,tmp.id,root); a[tmp.id].erase(a[tmp.id].begin()); } if(size[root]==2) {puts("Yazid is angry.");continue;} succ(root,0);printf("%d\n",val[su]);succ(root,val[su]); splay(su,root);splay(1,c[root][0]);del(1,c[1][1]); } if (op==2){ node1 tmp; while(!q.empty()&&q.top().t<=t) { tmp=q.top();q.pop(); insert1(root,tmp.id,root); a[tmp.id].erase(a[tmp.id].begin()); } int id=read(); int xx=find(root,id); if (xx){ puts("Succeeded!");pre(root,id);succ(root,id); splay(su,root);splay(pr,c[root][0]);del(pr,c[pr][1]); }else if(a[id].size()) { printf("%d\n",a[id].front().t-t); } else puts("YJQQQAQ is angry."); } if (op==3){ node1 tmp; while(!q.empty()&&q.top().t<=t) { tmp=q.top();q.pop(); insert1(root,tmp.id,root); a[tmp.id].erase(a[tmp.id].begin()); } int l=read(),r=read(); pre(root,l),succ(root,r); splay(su,root);splay(pr,c[root][0]);printf("%d\n",size[c[pr][1]]); } } } return 0;}

leoly的线段树版本 就是我的splay其实完全可以替换为线段树或者树状数组拥有更多的常数优势 代码简短好写

#include#include#include#include#define N 100010#define pa(a, b) (data){a, b}using namespace std;struct data{int x, id;};int n, sum[N*4], T, w[N], m, x, temp, y, L, R;dequeson[N];inline char gc(){ static char now[1<<16], *S, *T; if(S==T){T=(S=now)+fread(now, 1, 1<<16, stdin); if(S==T)return EOF;} return *S++;}inline int read(){ int x=0; char ch=gc(); while(ch<'0'||ch>'9')ch=gc(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=gc();} return x;}inline bool operator>(data a, data b){return a.x>b.x;}inline void ins(int i, int x, int L, int R){ sum[i]++; if(L==R)return; int mid=(L+R)>>1; if(x<=mid)ins(i<<1, x, L, mid); else ins((i<<1)|1, x, mid+1, R);}inline int cp(int i, int L, int R){ if(!sum[i])return 0; sum[i]--; if(L==R)return L; int mid=(L+R)>>1; if(sum[i<<1])return cp(i<<1, L, mid); else return cp((i<<1)|1, mid+1, R);}inline int check(int i, int x, int L, int R){ if(!sum[i])return 0; if(L==R){sum[i]--; return 1;} int mid=(L+R)>>1, s; s=x<=mid?check(i<<1, x, L, mid):check((i<<1)|1, x, mid+1, R); sum[i]-=s; return s;}inline int csum(int i, int a, int b, int L, int R){ if(a<=L&&R<=b)return sum[i]; int mid=(L+R)>>1, s=0; if(a<=mid)s+=csum(i<<1, a, b, L, mid); if(mid, greater >q; for(int i=1; i<=n; i++)son[i].clear(); memset(sum, 0, sizeof(sum)); m=read(); for(int i=1; i<=m; i++){ x=read(); temp=read(); while(q.size()&&q.top().x<=x){ y=q.top().id; ins(1, y, 1, n); son[y].pop_front(); q.pop(); } if(!temp){y=read(); son[y].push_back(x+w[y]); q.push(pa(x+w[y], y));} if(temp==1){ if(!sum[1]){printf("Yazid is angry.\n"); continue;} printf("%d\n", cp(1, 1, n)); } if(temp==2){ y=read(); if(check(1, y, 1, n)){printf("Succeeded!\n"); continue;} if(son[y].size()){printf("%d\n", son[y].front()-x); continue;} printf("YJQQQAQ is angry.\n"); } if(temp==3){L=read(); R=read(); printf("%d\n", csum(1, L, R, 1, n));} } } return 0;}

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