This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <algorithm>
using namespace std;
int N;
long long L;
struct data{
int num;
long long x,y;
}a[100002],b[100002];
bool cmpx(data x,data y){
if(x.x != y.x) return x.x < y.x;
return x.y < y.y;
}
bool cmpy(data x,data y){
if(x.y != y.y) return x.y < y.y;
return x.x < y.x;
}
int where[100002];
long long d[100002][2];
bool check[100002][2];
long long length(int x){
long long ans;
ans = a[x].x-a[x].y;
if(ans < 0) ans = -ans;
return ans+L;
}
void dfs(int x,int op){
int left,mid,right;
int i,v,t;
if(check[x][op]) return;
check[x][op] = true;
v = -1;
left = 1; right = N;
if(op == 0){
while(left <= right){
mid = (left+right)/2;
if(a[mid].x == a[x].x){
if(a[x].y < a[mid].y){
v = mid;
right = mid-1;
}else left = mid+1;
}else if(a[mid].x > a[x].x) right = mid-1;
else left = mid+1;
}
if(v == -1){ d[x][op] = length(x); return; }
t = v;
for(i=t; i<=N; i++){
if(a[x].x != a[i].x) break;
dfs(v,1);
d[x][op] = max(d[v][1]+length(x),d[x][op]);
}
}else{
while(left <= right){
mid = (left+right)/2;
if(a[x].y == b[mid].y){
if(a[x].x < b[mid].x){
v = mid;
right = mid-1;
}else left = mid+1;
}else if(b[mid].y > a[x].y) right = mid-1;
else left = mid+1;
}
if(v == -1){ d[x][op] = length(x); return; }
t = v;
for(i=t; i<=N; i++){
if(a[x].y != b[i].y) break;
v = where[b[v].num];
dfs(v,0);
d[x][op] = max(d[v][0]+length(x),d[x][op]);
}
}
}
int main(){
int i;
long long ans = 0;
//freopen("input.txt","r",stdin);
scanf("%d %lld",&N,&L);
for(i=1; i<=N; i++){
scanf("%lld %lld",&a[i].x,&a[i].y);
b[i].x = a[i].x;
b[i].y = a[i].y;
a[i].num = b[i].num = i;
}
sort(a+1,a+N+1,cmpx);
sort(b+1,b+N+1,cmpy);
for(i=1; i<=N; i++) where[a[i].num] = i;
for(i=1; i<=N; i++){
dfs(i,0);
dfs(i,1);
ans = max(ans,d[i][0]);
ans = max(ans,d[i][1]);
}
printf("%lld",ans);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |