求助! SBT 10分 MLE
  • 板块P2073 送花
  • 楼主Setoff
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/5/24 18:42
  • 上次更新2023/11/4 22:46:53
查看原帖
求助! SBT 10分 MLE
124628
Setoff楼主2021/5/24 18:42

RTRT, 只有 1010 分, 数组开大开小都是 MLEMLE

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;
#define fore(i,now) for(reg int i=head[now];i;i=e[i].nxt)
#define fora(i,a,b,c) for(reg int i=a;i<=b;i+=c)
#define forb(i,a,b,c) for(reg int i=a;i>=b;i-=c)
#define uLL unsigned LL
#define INF 0x3f3f3f3f
#define LL long long
#define reg register
#define N 100000005
#define R read()
inline LL read(){
    LL s=0, f=1; char c=getchar();
    while(c<'0'||c>'9') { if(c=='-') f=-f; c=getchar(); }
    while(c>='0'&&c<='9') s=(s<<3)+(s<<1)+(c^48), c=getchar();
    return s*f;
}
struct SBT {
    struct Value {
        int bp, pr;
        friend bool operator < (const Value &a, const Value &b)
            { return a.pr<b.pr; }
        friend bool operator > (const Value &a, const Value &b)
            { return a.pr>b.pr; }
        friend bool operator == (const Value &a, const Value &b)
            { return a.pr==b.pr; }
        friend bool operator >= (const Value &a, const Value &b)
            { return a.pr>=b.pr; }
    } t;
    struct SBTNode {
        Value val; int siz, lson, rson;
    } tree[N];
    int top, rot;
    SBT(int rot, int top)
        { this->rot=rot, this->top=top; }
    inline Value MakeValue(int bp, int pr){
        Value var; var.bp=bp; var.pr=pr; return var;
    }
    inline void LRotate(int &x){
        int y=tree[x].rson;
        tree[x].rson=tree[y].lson;
        tree[y].lson=x;
        tree[y].siz=tree[x].siz;
        tree[x].siz=tree[tree[x].lson].siz+tree[tree[x].rson].siz+1;
        x=y;
    }
    inline void RRotate(int &x){
        int y=tree[x].lson;
        tree[x].lson=tree[y].rson;
        tree[y].rson=x;
        tree[y].siz=tree[x].siz;
        tree[x].siz=tree[tree[x].lson].siz+tree[tree[x].rson].siz+1;
        x=y;
    }
    void Maintain(int &x, int f){
        if(!f){
            if(tree[tree[tree[x].lson].lson].siz>tree[tree[x].rson].siz)
                RRotate(x);
            else if(tree[tree[tree[x].lson].rson].siz>tree[tree[x].rson].siz)
                LRotate(tree[x].lson), RRotate(x);
            else return ;
        }else{
            if(tree[tree[tree[x].rson].rson].siz>tree[tree[x].lson].siz)
                LRotate(x);
            else if(tree[tree[tree[x].rson].lson].siz>tree[tree[x].lson].siz)
                RRotate(tree[x].rson), LRotate(x);
            else return ;
        }
        Maintain(tree[x].lson, 0);
        Maintain(tree[x].rson, 1);
        Maintain(x, 0);
        Maintain(x, 1);
    }
    void Insert(int &x, Value val){
        if(!x){
            x=++top;
            tree[x].lson=tree[x].rson=0;
            tree[x].val=val;
            tree[x].siz=1;
            return ;
        }
        ++tree[x].siz;
        if(val<tree[x].val) Insert(tree[x].lson, val);
        else Insert(tree[x].rson, val);
        Maintain(x, val>=tree[x].val);
    }
    Value SearchK(int &x, int k){
        int r=tree[tree[x].lson].siz+1;
        if(r==k) return tree[x].val;
        if(r>=k) return SearchK(tree[x].lson, k);
        return SearchK(tree[x].rson, k-r);
    }
    Value Erase(int &x, Value val){
        Value vl; --tree[x].siz;
        if((val==tree[x].val)||(val<tree[x].val&&!tree[x].lson)||(val>tree[x].val&&!tree[x].rson)){
            vl=tree[x].val;
            if(tree[x].lson&&tree[x].rson)
                tree[x].val=Erase(tree[x].lson, MakeValue(tree[x].val.bp, tree[x].val.pr+1));
            else x=tree[x].lson+tree[x].rson;
        }
        else if(val<tree[x].val) vl=Erase(tree[x].lson, val);
        else vl=Erase(tree[x].rson, val);
        return vl;
    }
} sbt(0, 0);
int main(){
    LL W=0, C=0;
    while(true){
        int op, w, c;
        if((op=R)==-1) break;
        if(op==1) W+=(w=R), C+=(c=R), sbt.Insert(sbt.rot, sbt.MakeValue(w, c));
        if(op==2){
            sbt.t=sbt.SearchK(sbt.rot, sbt.top);
            W-=sbt.t.bp; C-=sbt.t.pr;
            sbt.Erase(sbt.rot, sbt.t);
        }
        if(op==3){
            sbt.t=sbt.SearchK(sbt.rot, 1);
            W-=sbt.t.bp; C-=sbt.t.pr;
            sbt.Erase(sbt.rot, sbt.t);
        }
    }
    printf("%lld %lld", W, C);
    return 0;
}
2021/5/24 18:42
加载中...