CodeForces/397A

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
On Segment's Own Points	★☆☆☆☆	答案正确	100	2015-02-28 13:28:11	数据类型（3）

• 来自寒假练习：2015 Winter Day 5 div1 G题
• 原题链接：http://codeforces.com/problemset/problem/397/A

题意

给出一堆区间，找出[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; } } }