QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#62195 | #2838. 2D Geometry | wave# | TL | 0ms | 0kb | C++ | 1.4kb | 2022-11-17 16:58:19 | 2022-11-17 16:58:22 |
Judging History
answer
#include<queue>
#include<cmath>
#include<vector>
#include<time.h>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define lp p<<1
#define rp (p<<1)+1
using namespace std;
template<typename T>void read(T &x){
x=0;int w=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
x=x*w;
}
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=4e5+5;
int n,m,a[N],b[N];
struct pp{
int x,y;
}t[N];
int cmp(pp aa,pp bb){
if(aa.x==bb.x)return aa.y<bb.y;
return aa.x<bb.x;
}
int pd(int mid){
int num=0;
for(int i=1;i<=m;i++){
if(b[i]-a[i]<=mid&&n-b[i]+a[i]<=mid)continue;
if(b[i]-a[i]<=mid)t[++num].x=a[i],t[num].y=b[i];
if(n-b[i]+a[i]<=mid){
t[++num].x=1;t[num].y=a[i];
t[++num].x=b[i];t[num].y=n+1;
}
}
sort(t+1,t+1+num,cmp);
if(t[1].x!=1)return 1;
int lr=t[1].y;
for(int i=1;i<=num;i++)
if(t[i].x<=lr)lr=max(lr,t[i].y);
if(lr==n+1) return 0;
return 1;
}
void solve(){
int ff=0;
for(int i=1;i<=m;i++){
read(a[i]);read(b[i]);
if(a[i]!=b[i])ff=1;
if(a[i]>b[i])swap(a[i],b[i]);
}
if(!ff){
printf("0\n");
return;
}
int l=1,r=n,ans=n;
while(l<=r){
int mid=(l+r)/2;
if(pd(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d\n",ans);
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF)solve();
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
3 0 0 0 1 0 2 3 0 0 0 1 1 0 6 0 0 0 1 0 2 0 3 1 1 1 2