#include<bits/stdc++.h>
#pragma GCC optimize("O6,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
const int maxn=300000+10,maxh=maxn*2;
int all[maxn][2],n,inf=1e9,kaf=(1<<20),sz,kk=(1<<19)-1,lnk[maxn][2];
vector<int>allb,allc,alla;
struct segment{
int ps[(1<<21)],sum[(1<<21)];
void clear(){
memset(ps,0,sizeof(ps));
memset(sum,0,sizeof(sum));
}
void upd(int i,int w){
i+=kaf;
sum[i]+=w;
i>>=1;
while(i>0){
sum[i]+=w;
ps[i]=min(ps[(i<<1)],sum[(i<<1)]+ps[(i<<1)^1]);
i>>=1;
}
return ;
}
}segsb,segpb,segsc,segpc;
void clear(){
segsb.clear();
segpb.clear();
segsc.clear();
segpc.clear();
}
void fastscan(int &number) {
register int c;
number = 0;
c = getchar();
for (; (c>47 && c<58); c=getchar())
number = number *10 + c - 48;
}
void vorod(){
fastscan(n);
alla.push_back(-1);
for(int i=0;i<n;i++){
fastscan(all[i][0]);
alla.push_back(all[i][0]);
}
for(int i=n-1;i>=0;i--){
fastscan(all[i][1]);
alla.push_back(all[i][1]);
}
sort(alla.begin(),alla.end());
alla.resize(unique(alla.begin(),alla.end())-alla.begin());
allb.resize(n);
allc.resize(n);
for(int i=0;i<n;i++){
fastscan(allb[i]);
}
for(int i=0;i<n;i++){
fastscan(allc[i]);
}
sort(allb.begin(),allb.end());
sort(allc.begin(),allc.end());
for(int i=0;i<n;i++){
lnk[i][0]=lower_bound(alla.begin(),alla.end(),all[i][0])-alla.begin();
lnk[i][1]=lower_bound(alla.begin(),alla.end(),all[i][1])-alla.begin();
}
sz=alla.size();
}
void inssufb(int ind){
segsb.upd(ind,1);
}
void inspsb(int ind){
segpb.upd(maxh-ind,1);
}
void inssufc(int ind){
segsc.upd(ind,1);
}
void inspsc(int ind){
segpc.upd(maxh-ind,1);
}
void insb(int w,int ind){
int l=lnk[w][ind];
segsb.upd(l,-1);
segpb.upd(maxh-l,-1);
}
void insc(int w,int ind){
int l=lnk[w][ind];
segsc.upd(l,-1);
segpc.upd(maxh-l,-1);
}
void eraseb(int w,int ind){
int l=lnk[w][ind];
segsb.upd(l,1);
segpb.upd(maxh-l,1);
}
void erasec(int w,int ind){
int l=lnk[w][ind];
segsc.upd(l,1);
segpc.upd(maxh-l,1);
}
bool ch(){
if(segpc.ps[1]<0||segsb.ps[1]<0||segsc.ps[1]<0||segpb.ps[1]<0){
return 0;
}
return 1;
}
bool check(int mid){
clear();
int l=0,r=0;
for(int i=0;i<n;i++){
while(l<sz&&alla[l]<allb[i]-mid){
l++;
}
inssufb(l);
while(r<sz&&alla[r]<=allb[i]+mid){
r++;
}
inspsb(r-1);
}
l=0,r=0;
for(int i=0;i<n;i++){
while(l<sz&&alla[l]<allc[i]-mid){
l++;
}
inssufc(l);
while(r<sz&&alla[r]<=allc[i]+mid){
r++;
}
inspsc(r-1);
}
for(int i=0;i<n;i++){
insb(i,0);
insc(i,1);
}
for(int i=0,j=n-1;i<n;i++,j--){
if(ch()==1){
return 1;
}
eraseb(i,0);
erasec(j,1);
insb(j,1);
insc(i,0);
}
return ch();
}
int solve(){
int low=-1,high=1e9+5,mid;
while(high-low>1){
mid=(high+low)/2;
if(check(mid)){
high=mid;
}else{
low=mid;
}
}
return high;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
vorod();
int mainres=inf;
mainres=solve();
swap(allb,allc);
mainres=min(mainres,solve());
cout<<mainres<<"\n";
}
Compilation message
Main.cpp: In function 'void fastscan(int&)':
Main.cpp:36:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
36 | register int c;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
471 ms |
68144 KB |
Output is correct |
2 |
Correct |
461 ms |
68092 KB |
Output is correct |
3 |
Correct |
417 ms |
68324 KB |
Output is correct |
4 |
Correct |
460 ms |
68264 KB |
Output is correct |
5 |
Correct |
438 ms |
68332 KB |
Output is correct |
6 |
Correct |
433 ms |
68328 KB |
Output is correct |
7 |
Correct |
462 ms |
68332 KB |
Output is correct |
8 |
Correct |
414 ms |
68436 KB |
Output is correct |
9 |
Correct |
462 ms |
68324 KB |
Output is correct |
10 |
Correct |
368 ms |
68180 KB |
Output is correct |
11 |
Correct |
456 ms |
68532 KB |
Output is correct |
12 |
Correct |
467 ms |
68180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
471 ms |
68144 KB |
Output is correct |
2 |
Correct |
461 ms |
68092 KB |
Output is correct |
3 |
Correct |
417 ms |
68324 KB |
Output is correct |
4 |
Correct |
460 ms |
68264 KB |
Output is correct |
5 |
Correct |
438 ms |
68332 KB |
Output is correct |
6 |
Correct |
433 ms |
68328 KB |
Output is correct |
7 |
Correct |
462 ms |
68332 KB |
Output is correct |
8 |
Correct |
414 ms |
68436 KB |
Output is correct |
9 |
Correct |
462 ms |
68324 KB |
Output is correct |
10 |
Correct |
368 ms |
68180 KB |
Output is correct |
11 |
Correct |
456 ms |
68532 KB |
Output is correct |
12 |
Correct |
467 ms |
68180 KB |
Output is correct |
13 |
Correct |
463 ms |
68324 KB |
Output is correct |
14 |
Correct |
374 ms |
68528 KB |
Output is correct |
15 |
Correct |
461 ms |
68328 KB |
Output is correct |
16 |
Correct |
462 ms |
68328 KB |
Output is correct |
17 |
Correct |
477 ms |
68180 KB |
Output is correct |
18 |
Correct |
430 ms |
68328 KB |
Output is correct |
19 |
Correct |
468 ms |
68328 KB |
Output is correct |
20 |
Correct |
463 ms |
68180 KB |
Output is correct |
21 |
Correct |
458 ms |
68440 KB |
Output is correct |
22 |
Correct |
464 ms |
68328 KB |
Output is correct |
23 |
Correct |
380 ms |
68140 KB |
Output is correct |
24 |
Correct |
455 ms |
68324 KB |
Output is correct |
25 |
Correct |
382 ms |
68328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
471 ms |
68144 KB |
Output is correct |
2 |
Correct |
461 ms |
68092 KB |
Output is correct |
3 |
Correct |
417 ms |
68324 KB |
Output is correct |
4 |
Correct |
460 ms |
68264 KB |
Output is correct |
5 |
Correct |
438 ms |
68332 KB |
Output is correct |
6 |
Correct |
433 ms |
68328 KB |
Output is correct |
7 |
Correct |
462 ms |
68332 KB |
Output is correct |
8 |
Correct |
414 ms |
68436 KB |
Output is correct |
9 |
Correct |
462 ms |
68324 KB |
Output is correct |
10 |
Correct |
368 ms |
68180 KB |
Output is correct |
11 |
Correct |
456 ms |
68532 KB |
Output is correct |
12 |
Correct |
467 ms |
68180 KB |
Output is correct |
13 |
Correct |
463 ms |
68324 KB |
Output is correct |
14 |
Correct |
374 ms |
68528 KB |
Output is correct |
15 |
Correct |
461 ms |
68328 KB |
Output is correct |
16 |
Correct |
462 ms |
68328 KB |
Output is correct |
17 |
Correct |
477 ms |
68180 KB |
Output is correct |
18 |
Correct |
430 ms |
68328 KB |
Output is correct |
19 |
Correct |
468 ms |
68328 KB |
Output is correct |
20 |
Correct |
463 ms |
68180 KB |
Output is correct |
21 |
Correct |
458 ms |
68440 KB |
Output is correct |
22 |
Correct |
464 ms |
68328 KB |
Output is correct |
23 |
Correct |
380 ms |
68140 KB |
Output is correct |
24 |
Correct |
455 ms |
68324 KB |
Output is correct |
25 |
Correct |
382 ms |
68328 KB |
Output is correct |
26 |
Correct |
780 ms |
68448 KB |
Output is correct |
27 |
Correct |
732 ms |
68420 KB |
Output is correct |
28 |
Correct |
879 ms |
68388 KB |
Output is correct |
29 |
Correct |
483 ms |
68328 KB |
Output is correct |
30 |
Correct |
656 ms |
68444 KB |
Output is correct |
31 |
Correct |
729 ms |
68176 KB |
Output is correct |
32 |
Correct |
628 ms |
68432 KB |
Output is correct |
33 |
Correct |
544 ms |
68436 KB |
Output is correct |
34 |
Correct |
798 ms |
68436 KB |
Output is correct |
35 |
Correct |
813 ms |
68416 KB |
Output is correct |
36 |
Correct |
671 ms |
68440 KB |
Output is correct |
37 |
Correct |
1162 ms |
68440 KB |
Output is correct |
38 |
Correct |
1190 ms |
68452 KB |
Output is correct |
39 |
Correct |
1152 ms |
68460 KB |
Output is correct |
40 |
Correct |
711 ms |
68408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5099 ms |
86836 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
471 ms |
68144 KB |
Output is correct |
2 |
Correct |
461 ms |
68092 KB |
Output is correct |
3 |
Correct |
417 ms |
68324 KB |
Output is correct |
4 |
Correct |
460 ms |
68264 KB |
Output is correct |
5 |
Correct |
438 ms |
68332 KB |
Output is correct |
6 |
Correct |
433 ms |
68328 KB |
Output is correct |
7 |
Correct |
462 ms |
68332 KB |
Output is correct |
8 |
Correct |
414 ms |
68436 KB |
Output is correct |
9 |
Correct |
462 ms |
68324 KB |
Output is correct |
10 |
Correct |
368 ms |
68180 KB |
Output is correct |
11 |
Correct |
456 ms |
68532 KB |
Output is correct |
12 |
Correct |
467 ms |
68180 KB |
Output is correct |
13 |
Correct |
463 ms |
68324 KB |
Output is correct |
14 |
Correct |
374 ms |
68528 KB |
Output is correct |
15 |
Correct |
461 ms |
68328 KB |
Output is correct |
16 |
Correct |
462 ms |
68328 KB |
Output is correct |
17 |
Correct |
477 ms |
68180 KB |
Output is correct |
18 |
Correct |
430 ms |
68328 KB |
Output is correct |
19 |
Correct |
468 ms |
68328 KB |
Output is correct |
20 |
Correct |
463 ms |
68180 KB |
Output is correct |
21 |
Correct |
458 ms |
68440 KB |
Output is correct |
22 |
Correct |
464 ms |
68328 KB |
Output is correct |
23 |
Correct |
380 ms |
68140 KB |
Output is correct |
24 |
Correct |
455 ms |
68324 KB |
Output is correct |
25 |
Correct |
382 ms |
68328 KB |
Output is correct |
26 |
Correct |
780 ms |
68448 KB |
Output is correct |
27 |
Correct |
732 ms |
68420 KB |
Output is correct |
28 |
Correct |
879 ms |
68388 KB |
Output is correct |
29 |
Correct |
483 ms |
68328 KB |
Output is correct |
30 |
Correct |
656 ms |
68444 KB |
Output is correct |
31 |
Correct |
729 ms |
68176 KB |
Output is correct |
32 |
Correct |
628 ms |
68432 KB |
Output is correct |
33 |
Correct |
544 ms |
68436 KB |
Output is correct |
34 |
Correct |
798 ms |
68436 KB |
Output is correct |
35 |
Correct |
813 ms |
68416 KB |
Output is correct |
36 |
Correct |
671 ms |
68440 KB |
Output is correct |
37 |
Correct |
1162 ms |
68440 KB |
Output is correct |
38 |
Correct |
1190 ms |
68452 KB |
Output is correct |
39 |
Correct |
1152 ms |
68460 KB |
Output is correct |
40 |
Correct |
711 ms |
68408 KB |
Output is correct |
41 |
Execution timed out |
5099 ms |
86836 KB |
Time limit exceeded |
42 |
Halted |
0 ms |
0 KB |
- |