#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC optimize("conserve-stack")
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define mask(k) (1<<k)
#define mp make_pair
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
inline int scan()
{
char c = getchar_unlocked();
int x = 0;
while (c < '0' || c > '9')
{
c = getchar_unlocked();
}
while (c >= '0' && c <= '9')
{
x = (x << 1) + (x << 3) + c - '0';
c = getchar_unlocked();
}
return x;
}
void phongbeo();
const int inf = 1e16;
const ll mod2 = 1e9 + 7;
const int mod1 = 998244353;
const ll base=67;
int add(int x,int y)
{
if(x+y>=mod2) x-=mod2;
if(x+y<0)x+=mod2;
return x+y;
}
struct icd
{
long double a;
int b;
};
struct ib
{
int a;
int b;
};
struct ic
{
int a, b, c;
};
struct id
{
int a, b, c, d;
};
struct ie
{
int a, b, c, d, e;
};
ll n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int i, s10, s12,k1,k2,k3,s11,t,lim,w,l,r,p ;
int kk;
int el = 19;
main()
{
if(fopen(task".inp","r"))
{
fin(task);
fou(task);
}
NHP
/// cin>>s1;
// modwwe
phongbeo();
// checktime
}
vector<int> a;
vector<int> d;
vector<int> b;
vector<int> c;
vector<int> sor;
int ac_lef[100001];
int ac_right[100001];
int nearest[200001];
int pre[200001];
int suf[200001];
int cost(int x,int y)
{
}
void inside(vector<int> a,vector<int> b,int x,int y)
{
for(int i=0; i<n; i++)
{
ac_lef[i]=n-(upper_bound(b.begin(),b.end(),a[i]+x)-b.begin())+1;/// can co it nhat bao nhieu con lon hon
ac_right[i]=n-(lower_bound(b.begin(),b.end(),a[i]-x)-b.begin());
/// ac_left<=x<=ac_right
}
for(int i=0; i<n; i++)
{
if(y==0)
{
if(n-i-1<ac_lef[i])///it nhat can ac_left canh lon hon => ac_left+i-1 ko dc do xuong
{
suf[min(ac_lef[i]+i-1,i+n-1)-n+1]++;
}
if(nearest[i]>i+ac_right[i])
{
pre[max(i+ac_right[i]+1,n-1)-n+1]++;
pre[i+1]--;
}
}
else if(i!=n-1)
{
if(i<ac_lef[i])
{
pre[max(i+n-ac_lef[i],i+1)]++;
}
if(nearest[i+n]<ac_right[i])
{
suf[min(i+n-ac_right[i]-1,n-1)]--;
suf[i+2]++;
}
}
}
}
void outside(vector<int> a,vector<int> b,int x,int y)
{
for(int i=0; i<n; i++)
{
ac_lef[i]=n-(upper_bound(b.begin(),b.end(),a[i]+x)-b.begin())+1;/// can co it nhat bao nhieu con lon hon
ac_right[i]=n-(lower_bound(b.begin(),b.end(),a[i]-x)-b.begin());
/// ac_left<=x<=ac_right
}
for(int i=0; i<n; i++)
{
if(y==0)
{
if(i==n-1) continue;
int least=nearest[i]-(i+1+n);
if(least<ac_lef[i])
{
pre[i+1]++;
pre[i+ac_lef[i]+1]--;
}
if(least>ac_right[i])
pre[i+1]++;
else
pre[i+ac_right[i]+2]++;
}
else
{
if(i==0) continue;
int least=(i)-nearest[i+n];
if(least<ac_lef[i])
{
suf[i]++;
if(i-ac_lef[i]>=0)
suf[i-ac_lef[i]]--;
}
if(least>ac_right[i])
suf[i]++;
else if(i-ac_right[i]-1>=0)
suf[i-ac_right[i]-1]++;
}
}
}
bool get()
{
for(int i=1; i<=n; i++)
pre[i]+=pre[i-1];
for(int i=n-1; i>=0; --i)
suf[i]+=suf[i+1];
for(int i=1; i<n; i++)
if(!pre[i]&&!suf[i])return 1;
for(int i=0; i<=n; i++)
pre[i]=suf[i]=0;
return 0;
}
bool solve(vector<int> b,vector<int> c,int x)
{
/// find l and r of i
inside(a,b,x,0);
outside(a,c,x,0);
inside(d,b,x,n);
outside(d,c,x,n);
if(get())return 1;
for(int i=0; i<n; i++)
{
if(abs(a[i]-b[i])>x) return 0;
}
for(int i=n-1; i>=0; --i)
if(abs(d[i]-c[n-1-i])>x) return 0;
return 1;
/// for(int i=1; i<=n; i++)
}
bool check(int x)
{
return (solve(b,c,x)|solve(c,b,x));
}
void phongbeo()
{
cin>>n;
a.resize(n);
d.resize(n);
b.resize(n);
c.resize(n);
for(int i=0; i<n; i++)
cin>>a[i];
for(int i=0; i<n; i++)
cin>>d[i];
l=0;
for(int i=n-1; i; i--)
{
while(l<n&&d[l]>=a[i])l++;
nearest[i]=min(l-1+n-1,i+n-1);
}
l=n-1;
for(int i=0; i<n; i++)
{
while(l&&a[l]>d[i]) l--;
nearest[i+n]=l+1;
}
for(int i=0; i<n; i++)
cin>>b[i];
for(int i=0; i<n; i++)
cin>>c[i];
sort(b.begin(),b.end());
sort(c.begin(),c.end());
l=0;
r=1e9;
while(l<=r)
{
int mid=l+r>>1;
if(check(mid))r=mid-1;
else l=mid+1;
}
cout<<r+1;
}
Compilation message
Main.cpp:75:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
75 | main()
| ^~~~
Main.cpp: In function 'long long int cost(long long int, long long int)':
Main.cpp:101:1: warning: no return statement in function returning non-void [-Wreturn-type]
101 | }
| ^
Main.cpp: In function 'void phongbeo()':
Main.cpp:247:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
247 | int mid=l+r>>1;
| ~^~
Main.cpp: In function 'int main()':
Main.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | #define fin(x) freopen(x".inp","r",stdin)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:79:9: note: in expansion of macro 'fin'
79 | fin(task);
| ^~~
Main.cpp:14:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | #define fou(x) freopen(x".ans","w",stdout)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:80:9: note: in expansion of macro 'fou'
80 | fou(task);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4432 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
4432 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4432 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
4432 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4432 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
4432 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
69 ms |
27784 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4432 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
4432 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
