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

## 用矩形扫描线+STL SET写了个，跑了1S，汗。。。

Posted by yzhw at 2009-09-24 21:41:18 on Problem 3277
```Source Code

Problem: 3277  User: yzhw
Memory: 5020K  Time: 938MS
Language: G++  Result: Accepted

Source Code
# include <iostream>
using namespace std;
# include <set>
# include <cstdio>
# include <cstdlib>
struct line
{
int id;
long long x;
bool sta;
};
struct node
{
long long p;
int count;
};
class cmp1
{
public:
bool operator()(node a,node b) const
{
return a.p>b.p;
}
};

line data[100000];
long long h[100000];
int cmp(const void *a,const void *b)
{
line *aa=(line *)a;
line *bb=(line *)b;
return aa->x-bb->x;
}
set<node,cmp1> res;
int main()
{
int num;
scanf("%d",&num);
for(int i=1;i<=num;i++)
{
scanf("%lld %lld %lld",&data[2*i-1].x,&data[2*i].x,&h[i]);
data[2*i-1].id=data[2*i].id=i;
data[2*i-1].sta=1;
data[2*i].sta=0;
}
qsort(data+1,2*num,sizeof(line),cmp);
long long total=0;
for(int i=1;i<2*num;i++)
{
if(data[i].sta)
{
node temp;
temp.count=1;
temp.p=h[data[i].id];
set<node,cmp1>::iterator it=res.find(temp);
if(it==res.end())
res.insert(temp);
else
{
temp=*it;
temp.count++;
res.erase(temp);
res.insert(temp);
}
}
else
{
node temp;
temp.count=1;
temp.p=h[data[i].id];
set<node,cmp1>::iterator it=res.find(temp);
if(it->count==1)
res.erase(temp);
else
{
temp=*it;
temp.count--;
res.erase(temp);
res.insert(temp);
}
}
if(data[i].x==data[i+1].x||res.empty()) continue;
total+=(data[i+1].x-data[i].x)*(res.begin()->p);
}
printf("%lld\n",total);
return 0;
}

```

Followed by: