/ Randle /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 1ms 204.0 KiB
#2 Accepted 1ms 316.0 KiB
#3 Accepted 1ms 312.0 KiB
#4 Accepted 1ms 332.0 KiB
#5 Accepted 1ms 316.0 KiB
#6 Accepted 1ms 316.0 KiB
#7 Accepted 32ms 1.324 MiB
#8 Accepted 33ms 1.309 MiB
#9 Accepted 32ms 1.309 MiB
#10 Accepted 32ms 1.324 MiB

代码

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
int k, n, m, maxx[200010], tag[200010], ans;
struct node
{
    int x, y, c;
}e[50010];
void pushup(int o)
{
    maxx[o] = max(maxx[o << 1], maxx[o << 1 | 1]);
}
bool cmp(node a, node b)
{
    if (a.y == b.y)return a.x > b.x;
    return a.y < b.y;
}
void pushdown(int o)
{
    if (tag[o])
    {
        tag[o << 1] += tag[o];
        tag[o << 1 | 1] += tag[o];
        maxx[o << 1] += tag[o];
        maxx[o << 1 | 1] += tag[o];
        tag[o] = 0;
    }
}
void update(int o, int l, int r, int x, int y, int v)
{
    if (x <= l && r <= y)
    {
        tag[o] += v;
        maxx[o] += v;
        return;
    }
    pushdown(o);
    int mid = (l + r) >> 1;
    if (x <= mid)update(o * 2, l, mid, x, y, v);
    if (y > mid)update(o * 2 + 1, mid + 1, r, x, y, v);
    pushup(o);
}
int query(int o, int l, int r, int x, int y)
{
    if (x <= l && r <= y)
        return maxx[o]; 
    pushdown(o);
    int mid = (l + r) >> 1, res = 0;
    if (x <= mid)
        res = max(res, query(o * 2, l, mid, x, y));
    if (y > mid)
        res = max(res, query(o * 2 + 1, mid + 1, r, x, y)); 
    return res;
}
int main()
{
    //freopen("htam.in","r",stdin);
    //freopen("htam.out","w",stdout);
    scanf("%d%d%d", &k, &n , &m);
    for (int i = 1; i <= k; i++)scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].c);
    sort(e + 1, e + 1 + k, cmp);
    for (int i = 1; i <= k; i++)
    {
        int temp = query(1, 1, n, e[i].x, e[i].y), res = 0;
        if (temp >= m)continue;
        if (temp + e[i].c <= m)res = e[i].c;
        else res = m - temp;
        ans += res;
        update(1, 1, n, e[i].x, e[i].y - 1, res);
    }
    printf("%d\n", ans);

    return 0;
}

信息

递交者
类型
递交
题目
公交与怪兽 T2
题目数据
下载
语言
C++
递交时间
2018-10-31 10:19:45
评测时间
2018-10-31 10:19:45
评测机
分数
100
总耗时
140ms
峰值内存
1.324 MiB