 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| 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 | |||||||||
不同价值的长度怎么处理的?我MLE- -|In Reply To:求救今天网络赛 F 题（Farming） Posted by:sybil_0603 at 2009-09-12 17:11:03 > 一直WA，找不到错了……谁能提供几组强力数组也好啊~~
> 方法：
> 1.以x坐标排序为扫描线，n个人也按照x坐标排序
> 2.每次，求相邻的两条扫描线之间的面积；
> 3.对于相邻的两条扫描线之间，用离散化y坐标的线段树确定矩形的高，两条扫描线之间的距离为宽
>
> 代码：
> #include <iostream>
> #include <algorithm>
> #include <cstring>
> using namespace std;
> #define N 60000
> #define M 30011
> struct node{
> int x1,x2,y1,y2;
> int s;
> };
>
> int tree[N*5];
> node p[M];
> int x[3*M];
> int y[3*M];
> int n,m;
> int pi[100];
> long long ans;
> int px,py;
>
> bool cmp(node a,node b){
> return a.x1 < b.x1 || (a.x1 == b.x1 && a.x2 < b.x2);
> }
>
> bool cmp1(int a,int b){
> return a<b;
> }
>
> void insert(int l,int r,int s,int t,int k,int pos){
> //cout<<y[l]<<" "<<y[r]<<" "<<s<<" "<<t<<endl;
> if (tree[pos] >= k) return;
> if (y[l] == s && y[r] == t && tree[pos] == -1) {
> tree[pos] = k;
> return;
> }
> if (r - l <= 1) {
> tree[pos] = max(tree[pos],k);
> return;
> }
>
> if (tree[pos] != 0){
> tree[pos<<1] = tree[(pos<<1)+1] = tree[pos];
> tree[pos] = 0;
> }
> int mid = (l+r)>>1;
> if (t <= y[mid]) insert(l,mid,s,t,k,pos<<1);
> else if (y[mid] <= s) insert(mid,r,s,t,k,(pos<<1)+1);
> else{
> insert(l,mid,s,y[mid],k,pos<<1);
> insert(mid,r,y[mid],t,k,(pos<<1)+1);
> }
> }
>
> long long getArea(int l,int r,int pos){
> long long res = 0;
> if (tree[pos] == -1) return 0;
> else if (r - l == 1 || tree[pos] > 0) {
> res = (long long)tree[pos]*(y[r]-y[l]);
> }
> else if (tree[pos] == 0){
> int mid = (l+r)>>1;
> res = getArea(l,mid,pos<<1)+getArea(mid,r,(pos<<1)+1);
> }
> return res;
> }
>
> int main(){
> int T,index = 0;
> scanf("%d",&T);
> while (T--){
> px = 0;
> py = 0;
> scanf("%d %d",&n,&m);
> for (int i=1 ;i<=m ;++i) scanf("%d",pi+i);
> for (int i=0 ;i<n ;++i) {
> scanf("%d %d %d %d %d",&p[i].x1,&p[i].y1,&p[i].x2,&p[i].y2,&p[i].s);
> x[px++] = p[i].x1; x[px++] = p[i].x2;
> y[py++] = p[i].y1; y[py++] = p[i].y2;
> }
> ans = 0;
> sort(p,p+n,cmp);
> sort(x,x+px,cmp1);
> sort(y,y+py,cmp1);
> int l = x[0],r;
> int j = 0;
> --py;
> for (int i=1 ;i<px; ++i){
> r = x[i];
> if (l == r) continue;
> while (j < n && p[j].x2 <= l) ++j;
> tree[1] = -1;
> int w = r-l;
> int d = j;
> while (d < n && p[d].x1 <= l && r <= p[d].x2) {
> //cout<<p[d].y1<<" "<<p[d].y2<<endl;
> insert(0,py,p[d].y1,p[d].y2,pi[p[d].s],1);
> ++d;
> }
> long long tmp = getArea(0,py,1);
> //cout<<tmp<<endl<<"end..."<<endl;
> ans += tmp*w;
> l = r;
> }
> printf("Case %d: %I64d\n",++index,ans);
> }
> return 0;
> }
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
