（以“分类:模拟与排序分类:离散化 ==摘要== {{信息题|On Segment's Own Points|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70787#problem...”为内容创建页面） |
小 （数据类型） |
||
| 第1行： | 第1行： | ||
[[分类:模拟与排序]][[分类:离散化]] | [[分类:模拟与排序]][[分类:离散化]] | ||
==摘要== | ==摘要== | ||
| − | {{信息题|On Segment's Own Points|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70787#problem/G|1|数据类型|3 | + | {{信息题|On Segment's Own Points|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70787#problem/G|1|100|数据类型|3|time=2015-02-28 13:28:11}} |
*来自寒假练习：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70787 2015 Winter Day 5 div1] G题 | *来自寒假练习：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70787 2015 Winter Day 5 div1] G题 | ||
*原题链接：http://codeforces.com/problemset/problem/397/A | *原题链接：http://codeforces.com/problemset/problem/397/A | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| On Segment's Own Points | ★☆☆☆☆ | 答案正确 | 100 | 2015-02-28 13:28:11 | 数据类型（3） |
给出一堆区间，找出[l,r]内不属于任何区间的部分。
离散化排序判断即可。注意每个点可能出现多次。
| 397A.cpp代码已折叠
展开折叠内容
|
|---|
#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<bitset>
#include<set>
#include<stack>
#include<sstream>
#include<utility>
using namespace std;
//数据类型//
#define llu unsigned long long
#define lld long long
//定义默认类型//
typedef lld num;
#define dsi(n) num n;scanf("%lld",&n)
#define si(n) scanf("%lld",&n)
//其它//
#define reset(x) memset(x,0,sizeof(x))
#define ci const num&
#define sqr(x) ((x)*(x))
#define f(i,n) for(num i=1;i<=n;++i)
#define ff(i,r,n) for(num i=r;i<=n;++i)
#define fi(n) f(i,n)
#define f0(i,n) for(num i=0;i!=n;++i)
#define fd(i,n) for(num i=n;i>=1;--i)
#define foreach(i,s) for(typeof(s.begin()) i=s.begin();i!=s.end();++i)
#define rforeach(i,s) for(typeof(s.rbegin()) i=s.rbegin();i!=s.rend();++i)
#define iforeach(i,s) int idx=0;for(typeof(s.begin()) i=s.begin();i!=s.end();++i,++idx)
#define Vector2 pair<num,num>
#define vector2(x,y) make_pair(x,y)
#define x first
#define y second
multiset<Vector2> s;//fixed:multi.//
num sgNum,steOpen=0;
int main()
{
dsi(n);
dsi(x);dsi(y);
s.insert(vector2(x,2));
s.insert(vector2(y,2));
fi(n-1)
{
dsi(l);dsi(r);
s.insert(vector2(l,0));
s.insert(vector2(r,1));
}
num ans=0;
foreach(i,s)
{
typeof(i) j=i;
++j;
if(j==s.end())
{
cout<<ans;
return 0;
}
if(i->y==0)++sgNum;
if(i->y==1)--sgNum;
if(i->y==2&&steOpen)
{
cout<<ans;
return 0;
}
if(i->y==2)
{
steOpen=1;
}
if(steOpen&&!sgNum)
{
ans+=j->x-i->x;
}
}
}
|
CloudLunar