luogu P2073 送花 线段树

思路&心路

一眼认定***提

写的比较慢,写了1小时吧

开心的交上去

卧槽,只有20?

不服不服,拿着题解的代码去对拍

Emma,<100没问题

100000数据错了,还只是错了一个数据

debug 啊debug啊

以为是数据是0的锅

终于早出了小样例

卧槽,这std不对啊,md

又换了个std

绝望的乱改一通

最后发现是tm vis数组开小了

其实第一遍就能过的

╮(╯▽╰)╭

代码

#include <iostream>
#include <cstdio>
#define ll long long 
#define ls rt << 1
#define rs rt << 1 | 1
using namespace std;
const int maxn = 1e5 + 7;
const int maxm = 4e5 + 7;
const int inf = 0x3f3f3f3f;

bool vis[maxn*10];
int js,gs;
struct node {
    int l, r, ma, mi;
    ll meili, jiazhi;
} e[maxm];

int read() {
    int x = 0, f = 1; char s = getchar();
    for (; s > '9' || s < '0'; s = getchar()) if (s == '-') f = -1;
    for (; s >= '0' && s <= '9'; s = getchar()) x = (x << 3) + (x << 1) + s - '0';
    return x * f;
}

void pushup(int rt) {
    e[rt].ma    = max(e[ls].ma, e[rs].ma);
    e[rt].mi    = min(e[ls].mi, e[rs].mi);
    e[rt].meili = e[ls].meili + e[rs].meili;
    e[rt].jiazhi= e[ls].jiazhi+ e[rs].jiazhi;
}

void build(int l, int r, int rt) {
    e[rt].l = l,e[rt].r = r,e[rt].mi = inf;
    if(l == r) return;
    int mid=(l + r) >> 1;
    build(l,mid,ls);
    build(mid+1,r,rs);
    pushup(rt);
}

void update(int L, int w, int c, int rt) {
    if(e[rt].l == e[rt].r) {
        e[rt].meili = w;
        e[rt].jiazhi = c;
        e[rt].ma = e[rt].mi = c;
        return;
    }
    int mid=(e[rt].l + e[rt].r) >> 1;
    if(L <= mid) update(L, w, c, ls);
    else update(L, w, c, rs);
    pushup(rt);
}

void find_min(int rt) {
    if(e[rt].l == e[rt].r) {
        vis[e[rt].jiazhi] = 0;
        e[rt].meili = 0;
        e[rt].jiazhi = 0;
        e[rt].ma = 0;
        e[rt].mi = inf;
        return;
    }
    if(e[ls].mi < e[rs].mi) find_min(ls);
    else find_min(rs);
    pushup(rt);
}

void find_max(int rt) {
    if(e[rt].l == e[rt].r) {
        vis[e[rt].jiazhi] = 0;
        e[rt].meili = 0;
        e[rt].jiazhi = 0;
        e[rt].ma = 0;
        e[rt].mi = inf;
        return; 
    }
    if(e[ls].ma > e[rs].ma) find_max(ls);
    else find_max(rs);
    pushup(rt);
}

int main() {
    build(1, 1e5, 1);
    while (233) {
        int tmp = read();
        if (tmp == 1) {
            int a = read(),b = read();
            if(!vis[b]) {
                vis[b] = 1;
                update(++ js, a, b, 1);
                gs++;
            }
        } else if (tmp == 2) {
            if(gs) {
                find_max(1);
                gs--;
            }
        } else if (tmp == 3) {
            if(gs) {
                find_min(1);
                gs--;
            }
        } else break;
    }
    cout << e[1].meili << " " << e[1].jiazhi << "\n";
    return 0;
}
全部评论

相关推荐

07-23 14:04
东北大学 C++
既然这样,为什么不点击就送呢
牛马88号:因为你合适。但有很多笔试就挂了、通过了再排序的
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务