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