线段树或者平面扫除法的一维情形

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 08：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：80 有效耗时：0ms

5555555555555555555555555555555555555555555555555555

用线段树。但是要注意输入数据a=b时必须忽略，我就因为这个wa了n次。

好东西..Wa了N次了..216..216..216..很不厚道地偷了第一个数据去看..结果...Interger>>Word...AC...

离散化+快排+二分查找，一定不会超时的^^

郁闷了…………偶用的是线段树 结果是这样：

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：运行时错误...| 错误号: 202 | 堆栈溢出错

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

ps: 后来 AC 了 把longint改成int64就AC了……

各位要是因为第7个点而还没AC的话 不妨试试。

用Heap也可以过 呵呵

烦死了

一直不过

最后cheat

不想做了

快排就是爽！

好写又好用。

procedure qsort(l,r:longint);

离散了，建立点事件，然后按时间快排

和usaco上的milking cow比较类似

不过这个做起来不如那个感觉好..那个11总觉得莫名其妙

• -!!!!!!!

不好意思

准备提交的……

是错的答案……

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct your
{
int x;
int y;
}q[20010];
bool cmp(your j,your k)
{
if(j.x==k.x)
{
return j.y<k.y;
}
else
{
return j.x<k.x;
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&q[i].x,&q[i].y);
}
sort(q+1,q+n+1,cmp);
int ans=0;
int lx=q[1].x;
int ly=q[1].y;
ans=q[1].y-q[1].x;
for(int i=1;i<=n;i++)
{
if(ly>=q[i].x)
{
if(ly<q[i].y)
{
ans=ans+q[i].y-ly;
ly=q[i].y;
}

}
else
{
lx=q[i].x;
ly=q[i].y;
ans=ans+q[i].y-q[i].x;
}
}
printf("%d",ans);
}

妈的，智障题

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct node{
long long l,r;
}a[20002];
long long n,x;
bool cmp(node A,node B){
if (A.l==B.l) return A.r<B.r;
else return A.l<B.l;
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&a[i].l,&a[i].r);
sort(a+1,a+n+1,cmp);
int ans=0;
for (int i=1;i<=n-1;i++)
if (a[i].r>=a[i+1].l) {
a[i+1].l=min(a[i].l,a[i+1].l),
a[i+1].r=max(a[i+1].r,a[i].r);
}
else ans+=a[i].r-a[i].l;
ans+=a[n].r-a[n].l;
printf("%d",ans);
}