P2073 送花

$STL\ yyds!$

敲了半天的 $Splay$ 无果后索性换 $stl$ ，没想到居然还跑进了最优解！？顺便学了一下 $map$

AC Code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long ll;
using namespace std;
const int MAXN=1e5+1;
const int INF=0x7f7f7f7f;
template<class T>
inline void underRead(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
map<ll,ll>M;
ll op,w,c;
ll res,ans;
/*int M,Idx,op;
struct Val
{
    int w,c;
};
struct Splay
{
    int chi[2],fa;
    int num,size;
    Val val;
}Tree[MAXN];
int Root;
int Vis[MAXN],ans;
inline void underPushUp(int x)
{
    Tree[x].size=Tree[Tree[x].chi[0]].size+Tree[Tree[x].chi[1]].size+Tree[x].num;
}
inline void underRotate(int x)
{
    int y=Tree[x].fa,z=Tree[y].fa;
    int k=Tree[y].chi[1]==x;
    Tree[z].chi[Tree[z].chi[1]==y]=x;
    Tree[x].fa=z;
    Tree[y].chi[k]=Tree[x].chi[k^1];
    Tree[Tree[x].chi[k^1]].fa=y;
    Tree[x].chi[k^1]=y;
    Tree[y].fa=x;
    underPushUp(y);
    underPushUp(x);
}
inline void Splay(int x,int k)
{
    while(Tree[x].fa!=k)
    {
        int y=Tree[x].fa,z=Tree[y].fa;
        if(z!=k)
            if((Tree[y].chi[1]==x)^(Tree[z].chi[1]==y))
                underRotate(x);
            else
                underRotate(y);
        underRotate(x);
    }
    if(!k) Root=x;
}
bool f;
inline void underInsert(Val x)
{
    int u=Root,p;
    while(u)
    {
        if(Tree[u].val.c==x.c)
        {  
            f=1;
            return ;
        }
        p=u;
        u=Tree[u].chi[x.c>Tree[u].val.c];
    }
    u=++Idx;
    if(p) Tree[p].chi[x.c>Tree[p].val.c]=u;
    Tree[u].val.c=x.c;
    Tree[u].val.w=x.w;
    Tree[u].size=1;
    Tree[u].fa=p;
    Tree[u].num=1;
    Splay(u,0);
}
inline void underInit()
{
    Root=++Idx;
    Tree[Root].fa=0;
    Tree[Root].num=1;
    Tree[Root].size=1;
    Tree[Root].val.c=INF;
    Val u;
    u.w=0,u.c=-INF;
    underInsert(u);
}
inline int underGetPre(int x)
{
    int u=Root,res,v=Root;
    while(u)
    {
        v=u;
        if(Tree[u].val.c<x)
        {
            res=u;
            u=Tree[u].chi[1];
        }
        else u=Tree[u].chi[0];
    }
    Splay(v,0);
    return res;
}
inline int underGetNxt(int x)
{
    int u=Root,res,v=Root;
    while(u)
    {
        v=u;
        if(Tree[u].val.c>x)
        {
            res=u;
            u=Tree[u].chi[0];
        }
        else u=Tree[u].chi[1];
    }
    Splay(v,0);
    return res;
}
inline void underErase(int x)
{
    int l=underGetPre(x),r=underGetNxt(x);
    Splay(l,0),Splay(r,l);
    Tree[Tree[r].chi[0]].fa=0;
    Tree[r].chi[0]=0;
    Splay(r,0);
}*/
int main()
{
    // freopen("splay.in","r",stdin);
    // freopen("splay.out","w",stdout);
    /*underInit();*/
    map<ll,ll>::iterator it;
    while(1)
    {
        underRead(op);
        if(op==-1) break;
        else if(op==1)
        {
            underRead(w),underRead(c);
            // if(M.count(c)) continue;
            M.insert(make_pair(c,w));
            /*Val Q;
            scanf("%d%d",&Q.w,&Q.c);
            f=0;
            underInsert(Q);
            if(f) Vis[Q.c]=Q.w;
            ans+=Q.w;*/
        }
        else if(op==3&&!M.empty())
        {
            it=M.begin();
            M.erase(it);
            /*int x=underGetPre(INF);
            if(!Vis[Tree[x].val.c]) continue;
            underErase(Tree[x].val.c);
            ans-=Vis[Tree[x].val.c];
            Vis[Tree[x].val.c]=0;*/
        }
        else if(op==2&&!M.empty())
        {
            it=M.end();
            M.erase(--it);
            /*int x=underGetNxt(-INF);
            if(!Vis[Tree[x].val.c]) continue;
            underErase(Tree[x].val.c);
            ans-=Vis[Tree[x].val.c];
            Vis[Tree[x].val.c]=0;*/
        }
    }
    for(map<ll,ll>::iterator i=M.begin();i!=M.end();i++)
    {
        ans+=(*i).second;
        res+=(*i).first;
    }
    printf("%lld %lld",ans,res);
    /*printf("%d",ans);*/
    return 0;
}
/*
1 1 1
1 2 5
2
1 3 3
3
1 5 2
-1
*/