#include <bits/stdc++.h>
#define f first
#define s second
#define sz(x) (int)(x).size()
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pw(x) (1LL<<(x))
#define m_p make_pair
#define fast_iati ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;
//const int lg=log2(300'000)+1;
const int N=3e6;
bool del[2*N];
struct segtree{
int mx[4*N];
vec<pii> wyfu;
segtree(){
fill(mx,mx+4*N,-1e9);
}
void init(){
sort(all(wyfu));
wyfu.erase(unique(all(wyfu)),wyfu.end());
}
int gi(pii x){
return upper_bound(all(wyfu),x)-wyfu.begin()-1;
}
void upd(int i,int x,int v,int tl,int tr){
if(tl==tr){
mx[v]=x;
return;
}
int tm=(tl+tr)>>1;
if(tm>=i)
upd(i,x,2*v,tl,tm);
else
upd(i,x,2*v+1,tm+1,tr);
mx[v]=max(mx[2*v],mx[2*v+1]);
}
int get(int l,int r,int v,int tl,int tr){
if(l>r)
return -1e9;
if(tl>=l&&tr<=r)
return mx[v];
if(tl>r||tr<l)
return -1e9;
int tm=(tl+tr)>>1;
return max(get(l,r,2*v,tl,tm),get(l,r,2*v+1,tm+1,tr));
}
void _debug(int v,int tl,int tr){
cout<<"SLOY "<<v<<' '<<tl<<' '<<tr<<' '<<mx[v]<<endl;
if(tl==tr)
return ;
int tm=(tl+tr)>>1;
_debug(2*v,tl,tm);
_debug(2*v+1,tm+1,tr);
}
}lft,rgt;
vec<int> kek;
vec<pii> wyfu;
map<pii,int>mp;
int tmr;
vec<pii> toadd[N];
vec<pii> todel[N];
void add(int l,int r,int t,int tp,int w=0){
if(l==r) return;
int mid=(l+r)>>1;
// cout<<"CHINGY "<<l<<' '<<r<<' '<<t<<endl;
if(!t){
del[mp[{l,tp}]]=1;
if(!w)
return ;
///r>=x
lft.upd(lft.gi({mid,tp}),-1e9,1,0,sz(lft.wyfu));
// cout<<"DEL LFT "<<mid<<' '<<-1e9<<' '<<tp<<endl;
///l<=x
rgt.upd(rgt.gi({mid+1,tp}),-1e9,1,0,sz(rgt.wyfu));
// cout<<"DEL RGT "<<mid+1<<' '<<-1e9<<' '<<tp<<endl;
return;
}
if(!w)
rgt.wyfu.pb({mid+1,tp}),lft.wyfu.pb({mid,tp});
mp[{l,tp}]=tmr;
if(w){
///r>=x
lft.upd(lft.gi({mid,tp}),-l,1,0,sz(lft.wyfu));
// cout<<"ADD LFT "<<-l<<" "<<mid<<' '<<tp<<endl;
///l<=x
rgt.upd(rgt.gi({mid+1,tp}),r,1,0,sz(rgt.wyfu));
// cout<<"ADD RGT "<<r<<' '<<mid+1<<' '<<tp<<endl;
}
++tmr;
}
const int Nax=3e5+1;
set<int> st[Nax];
vec<int>here[Nax];
signed main(){
fast_iati;
int n,q,k;
n=3e5;
q=3e5;
k=100;
// cin>>n>>k>>q;
vec<array<int,3>>arr;
vec<int>x(n),a(n),b(n),t(n);
for(int i=0;i<n;i++){
// cin>>x[i]>>t[i]>>a[i]>>b[i];
x[i]=rand(),t[i]=rand()%k+1;
a[i]=rand(),b[i]=rand();
if(a[i]>b[i])
swap(a[i],b[i]);
arr.push_back({a[i],0,i});
arr.push_back({b[i]+1,-1,i});
--t[i];
here[t[i]].pb(i);
}
vec<int>l(q),y(q);
for(int i=0;i<q;i++){
// cin>>l[i]>>y[i];
l[i]=rand(),y[i]=rand();
arr.push_back({y[i],2,i});
}
sort(all(arr));
auto stupid=[&](array<int,3> z){
pii me={-1e9,0};
int tx=l[z[1]];
for(int j=0;j<k;j++){
if(sz(st[j])==2) continue;
auto it=st[j].lower_bound(tx);
int omn=2e9;
if(it!=st[j].end()) umin(omn,*it-tx);
if(it!=st[j].begin()) umin(omn,tx-*prev(it));
// cout<<"COLOUR "<<j<<' '<<omn<<' '<<tx<<endl;
umax(me.f,omn);me.s++;
}
return me;
};
vec<int>cnt(k,0);
for(int i=0;i<k;i++){
add(-3e8,3e8,1,i);
st[i].insert(-3e8);st[i].insert(3e8);
}
int total=0;
vec<bool>bad(q,0);
int j=0;
for(auto &z : arr){
swap(z[1],z[2]);
if(z[2]==2){
bad[z[1]]=(total==k?0:1);
continue;
}
// cout<<"AUE "<<endl;
if(z[2]==-1){
int i=z[1];
auto it=st[t[i]].lower_bound(x[i]);
todel[j].pb({x[i],*next(it)});
todel[j].pb({*prev(it),x[i]});
toadd[j].pb({*prev(it),*next(it)});
add(x[i],*next(it),0,t[i]);
add(*prev(it),x[i],0,t[i]);
add(*prev(it),*next(it),1,t[i]);
st[t[i]].erase(it);
cnt[t[i]]--;
if(!cnt[t[i]])
total--;
}
else{
int i=z[1];
if(!cnt[t[i]])
total++;
cnt[t[i]]++;
st[t[i]].insert(x[i]);
auto it=st[t[i]].lower_bound(x[i]);
add(*prev(it),*next(it),0,t[i]);
add(x[i],*next(it),1,t[i]);
add(*prev(it),x[i],1,t[i]);
toadd[j].pb({x[i],*next(it)});
toadd[j].pb({*prev(it),x[i]});
todel[j].pb({*prev(it),*next(it)});
}
j++;
// cout<<z[0]<<' '<<total<<endl;
}
// cout<<"HERE \n";
// cout<<endl;
j=0;
///building
lft.init();
rgt.init();
vec<int> ansq(q,-1);
// assert(total==0);
for(auto &z : arr){
if(z[2]==2){
int i=z[1];
if(bad[i])
continue;
int what=0;
///r>=x
umax(what,l[i]+lft.get(lft.gi(m_p(l[i],-2e9))+1,sz(lft.wyfu),1,0,sz(lft.wyfu)));
// cout<<"AFTER L "<<what<<' '<<lft.gi(m_p(l[i],-2e9))+1<<endl;
///x>=l
umax(what,-l[i]+rgt.get(0,rgt.gi(m_p(l[i],2e9)),1,0,sz(rgt.wyfu)));
// cout<<"AFTER R "<<what<<endl;
ansq[i]=what;
continue;
}
int i=z[1];
for(auto &z : todel[j])
add(z.f,z.s,0,t[i],1);
for(auto &z : toadd[j])
add(z.f,z.s,1,t[i],1);
j++;
// cout<<"DEBUG "<<endl;
// lft._debug(1,0,sz(lft.wyfu));
// cout<<z[0]<<' '<<total<<endl;
}
for(auto &z : ansq)
cout<<z<<'\n';
return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7
1 1 1
100000000 1 1 1
1 1
*/
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:133:10: warning: variable 'stupid' set but not used [-Wunused-but-set-variable]
133 | auto stupid=[&](array<int,3> z){
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5024 ms |
351476 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5024 ms |
351476 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5084 ms |
351488 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5091 ms |
351332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5024 ms |
351476 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5024 ms |
351476 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
