| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
为什么一直是Runtime Error啊,有人能告诉我为什么嘛? #3277#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator