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 |
Re:谁帮我检查一下 一定重谢In Reply To:wa Posted by:hzsmajia at 2007-09-27 20:02:44 #include <stdio.h> #include <algorithm> struct H { int s, e, h; }h[40005]; int a[80010]; int m; struct { int l, r, h; int cov; __int64 areal, arear, area; }tree[8*80010]; int s, e; inline int cmp(H a, H b) { return a.h < b.h; } void construct(int now, int left, int right) { tree[now].l = left; tree[now].r = right; tree[now].h = 0; tree[now].cov = 0; tree[now].area = 0; tree[now].areal = 0; tree[now].arear = 0; if(left + 1 < right) { int mid = (left + right) >> 1; construct(2*now, left , mid); construct(2*now+1, mid, right); } } int binsea(int c) { int l = 1, r = m; while(l < r) { int mid = (l + r) >> 1; if(a[mid] >= c) r = mid; else l = mid+1; } return l; } __int64 inserttree(int now, int h) { int mid = (tree[now].l + tree[now].r) >> 1; if(s <= tree[now].l && e >= tree[now].r ) { tree[now].h = h; tree[now].cov = 1; // printf("now %d %d\n", now, h); tree[now].areal = h*(a[mid] - a[tree[now].l]); tree[now].arear = h*(a[tree[now].r] - a[mid]); tree[now*2].area = tree[now].areal; tree[now*2+1].area = tree[now].arear; tree[now*2].cov = 1; tree[now*2+1].cov = 1; return tree[now].area = tree[now].areal + tree[now].arear; } if(tree[now].cov == 1) { tree[now].areal = tree[now].h*(a[mid] - a[tree[now].l]); tree[now].arear = tree[now].h*(a[tree[now].r] - a[mid]); if(tree[now].l + 1 < tree[now].r) { tree[now*2].area = tree[now].areal; tree[now*2+1].area = tree[now].arear; tree[now*2].cov = 1; tree[now*2+1].cov = 1; } } tree[now].cov = -2; if(s < mid) tree[now].areal = inserttree(2*now, h); if(e > mid) tree[now].arear = inserttree(2*now+1, h); return tree[now].area = tree[now].areal + tree[now].arear; } int main() { #ifndef ONLINE_JUDGE freopen ("3277.txt","r",stdin); #endif int i, n; scanf("%d", &n); m = 1; for(i=0; i < n; i++) { scanf("%d %d %d",&h[i].s, &h[i].e, &h[i].h); a[m++] = h[i].s; a[m++] = h[i].e; } std::sort(a+1, a+m); std::sort(h, h+n, cmp); int j = 1; for(i = 2; i < m; i++) { if(a[i] != a[j]) { j ++; a[j] = a[i]; } } m = j ; // printf("m %d\n", m); construct(1, 1, m); for(i=0; i < n; i++) { s = binsea(h[i].s); e = binsea(h[i].e); // printf("%d %d\n", s, e); inserttree(1, h[i].h); // printf("area %I64d\n", tree[1].area); } printf("%I64d\n", tree[1].area); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator