火锅盛宴

Author Avatar
ZC 2月 02, 2019
  • 在其它设备中阅读本文章

火锅盛宴

听了jz学长的讲解才会的$ Q \omega Q$

jz学长搬题出的题面(和原来意思一样)

简单的题解:

#include<cstdio>
#include<queue>
#include<cstring>
namespace FastIO{struct Reader{char buf[1<<20],*s,*t;bool EOF_FLG;Reader():s(buf),t(buf),EOF_FLG(false) {};char gt() {return s==t&&((t=(s=buf)+fread(buf,1,1<<20,stdin))==s)?EOF:(*s++);}Reader& operator>>(char* str) {if(EOF_FLG)return *str=0,*this;while((*str=gt())!=' '&&*str!='\n'&&*str!=EOF)++str;if(*str==EOF)EOF_FLG=true;*str=0;return *this;}template<typename T>Reader&operator>>(T&x) {if(EOF_FLG)return *this;char c=0,d;while(c!=EOF&&(c<'0'||c>'9'))d=c,c=gt();if(c==EOF){EOF_FLG=true;return *this;}else x=0;while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=gt();if(d=='-')x=-x;return *this;}}in;struct Writer{char buf[1<<20],*s,*t;Writer():s(buf),t(buf+(1<<20)){}~Writer(){fwrite(buf,1,s-buf,stdout);}void pt(char c){(s==t)?(fwrite(s=buf,1,1<<20,stdout),*s++=c):(*s++=c);}template<typename T>Writer&operator<<(T x){if(!x)return pt('0'),*this;if(x<0)pt('-'),x=-x;char a[40],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');return *this;}Writer&operator<<(const char*s) {while(*s)pt(*s++);return *this;}}out;}using namespace FastIO;
#define Fur(i,x,y) for(register int i=x;i<=y;i++)
#define clr(x,y) memset(x,y,sizeof(x))
using namespace std;
#define N 100000
int tr[1<<20],ti[N+1],cnt[N+1],T,n,m,mx;
vector<int>b[N+1];
int get(int x){int s=0;while(x)s+=tr[x],x-=(x&-x);return s;}
void upd(int pos,int v){while(pos<=mx){tr[pos]+=v;pos+=(pos&-pos);}}
struct node{int t,v;};
bool operator < (node x,node y){return x.t>y.t;}
priority_queue<node>q;
int main(){
in>>T;
while(T--){
    in>>n;
    clr(tr,0);clr(cnt,0);
    Fur(i,1,n)b[i].clear();
    while(!q.empty())q.pop();
    for(mx=1;mx<n;mx<<=1);

    Fur(i,1,n)in>>ti[i];
    in>>m;
    int x,l,r,k,t,ty;node tmp;
    while(m--){
        in>>t>>ty;
        while(!q.empty()&&(tmp=q.top()).t<=t)
            upd(tmp.v,1),
            cnt[tmp.v]++,
            q.pop();
        if(ty==0)
            in>>x,
            q.push((node){t+ti[x],x}),
            b[x].push_back(t+ti[x]);
        if(ty==1){
            if(!tr[mx]){out<<"Yazid is angry.\n";continue;}
            l=0;r=mx;k=1;
            while(l<r){
                int mid=(l+r)>>1;
                if(tr[mid]>=k)r=mid;
                else l=mid+1,k-=tr[mid];
            }
            out<<l<<"\n";upd(l,-1);
        }
        if(ty==2){
            in>>x;
            if(get(x)-get(x-1)){
                upd(x,-1);
                out<<"Succeeded!\n";
            }
            else{
                if(cnt[x]==(int)b[x].size())out<<"YJQQQAQ is angry.\n";
                else out<<b[x][cnt[x]]-t<<"\n";
            }
        }
        if(ty==3)
            in>>l>>r,
            out<<get(r)-get(l-1)<<"\n";
    }
}
}