Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

用矩形扫描线+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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator