> 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;
> } 
>