Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

为什么一直是Runtime Error啊,有人能告诉我为什么嘛? #3277

Posted by 18724088901 at 2019-12-19 12:03:06
#include <iostream>
#include <algorithm>
using namespace std;
struct building
{
    long long x, y, h;
};
// #define debug cout
const long long maxsize = 40000 + 5;
building tree[4 * maxsize];
// long long tag[maxsize];
long long segments[2 * maxsize];
long long tag[4 * maxsize];

building buildings[maxsize];
void pushup(long long root)
{
    tree[root].x = tree[root * 2].x;
    tree[root].y = tree[root * 2 + 1].y;
    if (tree[root * 2].h == tree[root * 2 + 1].h)
    {
        tree[root].h = tree[root * 2].h;
    }
    else
        tree[root].h = 0;
}
void pushdown(long long root)
{
    if (tag[root])
    {
        tree[root * 2 + 1].h = tag[root];
        tree[root * 2].h = tag[root];
        tree[root].h = 0;
        tag[root * 2] = tag[root];
        tag[root * 2 + 1] = tag[root];
        tag[root] = 0;
    }
}
void buildtree(long long root, long long l, long long r)
{
    if (l == r)
    {
        tree[root].x = segments[l];
        tree[root].y = segments[l + 1];
        tree[root].h = 0;
        // tag[root] = 0;
        // debug << root << " " << tree[root].x << " " << tree[root].y << endl;
        return;
    }
    long long mid = (l + r) / 2;
    buildtree(root * 2, l, mid);
    buildtree(root * 2 + 1, mid + 1, r);
    pushup(root);
    // debug << root << " " << tree[root].x << " " << tree[root].y << endl;
}
void update(long long root, long long L, long long R, long long l, long long r, long long c)
{
    if (r <= tree[root].x)
        return;
    if (l >= tree[root].y)
        return;
    // debug << "root: " << root << " L R:" << tree[root].x << " " << tree[root].y << " " << l << " " << r << " " << c << endl;
    pushdown(root);
    if (l <= tree[root].x && r >= tree[root].y)
    {
        tree[root].h = c;
        tag[root] = c;
        return;
    }
    long long mid = (L + R) / 2;
    // if (r < tree[root].y)
    update(root * 2, L, mid, l, r, c);
    // if (l > tree[root].x)
    update(root * 2 + 1, mid + 1, R, l, r, c);
    pushup(root);
}
long long iter(long long root, long long L, long long R)
{
    // if (tag[root])
    // debug << root << " h: " << tree[root].h << " x y: " << tree[root].x << " " << tree[root].y << endl;
    if (tree[root].h != 0)
    {
        return tree[root].h * (tree[root].y - tree[root].x);
    }
    if (L == R)
    {
        return tree[root].h * (tree[root].y - tree[root].x);
    }
    long long mid = (L + R) / 2;
    return iter(root * 2, L, mid) + iter(root * 2 + 1, mid + 1, R);
}
int main()
{
    long long num_building;
    cin >> num_building;
    long long bs, be, bh;
    for (long long i = 1; i <= num_building; i++)
    {
        cin >> bs >> be >> bh;
        segments[i] = buildings[i].x = bs;
        segments[num_building + i] = buildings[i].y = be;
        buildings[i].h = bh;
    }
    sort(segments + 1, segments + 2 * num_building);
    long long j = 1;
    for (long long i = 1; i <= 2 * num_building; i++)
    {
        if (segments[j] != segments[i])
        {
            segments[++j] = segments[i];
        }
    }
    j -= 2;
    buildtree(1, 1, j);
    for (long long i = 1; i <= num_building; i++)
    {
        update(1, 1, j - 1, buildings[i].x, buildings[i].y, buildings[i].h);
    }
    long long ret = iter(1, 1, j);
    cout << ret << endl;
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator