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;
}
全部评论

相关推荐

06-12 17:46
门头沟学院 Java
运营你豪哥:来说重点: ​1.项目前置,时间倒序。​​ 2.​项目描述强化结果与量化效果(STAR原则里的R)。​​ ​3.个人技能精炼,明确掌握程度,突出核心。​​ ​4.增加强有力开头的个人总结部分。​​ 5.​优化教育背景(成绩排名)、合并奖项与活动。​​
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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