xindoo is
always here

codeforces 272C. Dima and Staircase(线段树)


题目链接

    题目很长,看加猜加谷歌翻译才看懂了题目。每级台阶的宽都是1,但高不同,并且告诉你了,然后给你m个箱子,长和宽都告诉你,把箱子靠左放,求箱子的底部有多高。

   因为都是放在最左边的,所以只要和最左边的高度比较,这样就不用更新线段树了。

代码:

//cf 272 C
//2013-05-14-20.26
#include <stdio.h>
using namespace std;

const int maxn = 100005;

struct node
{
    int l, r, mid;
    __int64 m;
}tree[maxn<<2];
__int64 a[maxn];

__int64 max(__int64 a, __int64 b)
{
    if (a > b)
        return a;
    return b;
}
void build(int l, int r, int o)
{
    tree[o].l = l;
    tree[o].r = r;
    int mid = (l+r)>>1;
    tree[o].mid = mid;
    if (l == r)
    {
        tree[o].m = a[l];
        return ;
    }
    build(l, mid, o<<1);
    build(mid+1, r, (o<<1)+1);
    tree[o].m = max(tree[o<<1].m, tree[(o<<1)+1].m);
}

int query(int l, int r, int o)
{
    if (l == tree[o].l && tree[o].r == r)
        return tree[o].m;
    if (r <= tree[o].mid)
        return query(l, r, o<<1);
    else if (l > tree[o].mid)
        return query(l, r, (o<<1)+1);
    else
        return max(query(l, tree[o].mid, o<<1), query(tree[o].mid+1, r, (o<<1)+1));
}

int main()
{
    int n, m;
    while (scanf("%d", &n) != EOF)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf("%I64d", &a[i]);
        }
        build(1, n, 1);
        __int64 high = a[1];
        scanf("%d", &m);
        __int64 w, h;
        while (m--)
        {
            scanf("%I64d %I64d", &w, &h);
            printf("%I64d\n", max(query(1, w, 1), high));
            high = max(query(1, w, 1), high) + h;
        }
    }
    return 0;
}





打赏
未经允许不得转载:XINDOO » codeforces 272C. Dima and Staircase(线段树)
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏