Submission #924635

#	Time	Username	Problem	Language	Result	Execution time	Memory
924635		winter0101	New Home (APIO18_new_home)	C++17	100 / 100	4736 ms	348452 KiB

new_home

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=3e5+9;
const int mx=2e8;
const int mn=-1e8;
set<int>cord[maxn];
multiset<int>dubi[maxn];
int n,k,q,line;
int now=0;
struct lne{
int l,r,tim;
bool operator < (const lne &p)const {
if (l==p.l&&r==p.r)return tim<p.tim;
if (l==p.l)return r<p.r;
return l<p.l;
}
};
multiset<lne>temp[maxn];
vector<pii>st[maxn*4];
void update(int id,int l,int r,int u,int v,const pii &x){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
st[id].pb(x);
return;
}
int mid=(l+r)>>1;
update(id<<1,l,mid,u,v,x);
update(id<<1|1,mid+1,r,u,v,x);
}
void add_line(int l,int r,int type,int tme){
temp[type].insert({l,r,tme});
}
void del_line(int l,int r,int type,int del){
auto it=temp[type].lower_bound({l,r,0});
auto tmp=(*it);
update(1,1,line,tmp.tim,del-1,{tmp.l,tmp.r});
temp[type].erase(it);
}
void add_point(int x,int type,int tme){
if (cord[type].empty())now++;
if (cord[type].find(x)!=cord[type].end()){
dubi[type].insert(x);
return;
}
if (cord[type].empty()){
cord[type].insert(x);
add_line(mn,x,type,tme);
add_line(x,mx,type,tme);
return;
}
auto it=cord[type].upper_bound(x);
if (it==cord[type].end()){
it--;
del_line((*it),mx,type,tme);
add_line(x,mx,type,tme);
add_line((*it),x,type,tme);
cord[type].insert(x);
return;
}
if (it==cord[type].begin()){
del_line(mn,(*it),type,tme);
add_line(x,(*it),type,tme);
add_line(mn,x,type,tme);
cord[type].insert(x);
return;
}
int l1,r1=(*it);
it--;
l1=(*it);
del_line(l1,r1,type,tme);
add_line(x,r1,type,tme);
add_line(l1,x,type,tme);
cord[type].insert(x);
return;
}
void del_point(int x,int type,int tme){
if (dubi[type].find(x)!=dubi[type].end()){
dubi[type].erase(dubi[type].find(x));
return;
}
if (sz(cord[type])==1)now--;
cord[type].erase(x);
if (cord[type].empty()){
del_line(mn,x,type,tme);
del_line(x,mx,type,tme);
return;
}
auto it=cord[type].upper_bound(x);
if (it==cord[type].end()){
it--;
del_line((*it),x,type,tme);
del_line(x,mx,type,tme);
add_line((*it),mx,type,tme);
return;
}
if (it==cord[type].begin()){
del_line(mn,x,type,tme);
del_line(x,(*it),type,tme);
add_line(mn,(*it),type,tme);
return;
}
int l1,r1=(*it);
it--;
l1=(*it);
del_line(l1,x,type,tme);
del_line(x,r1,type,tme);
add_line(l1,r1,type,tme);
return;
}
struct store{
int x,t,a,b;
}a[maxn];
pii b[maxn];
vector<int>add[maxn*3],del[maxn*3];
vector<int>answer[maxn*3];
int st1[maxn*4],st2[maxn*4],c[maxn];
/*
1 for a-x
2 for x-a
*/
void build(int id,int l,int r){
st1[id]=mx,st2[id]=mn;
if (l==r)return;
int mid=(l+r)>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
}
void upd1(int id,int l,int r,int u,int v,int val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
st1[id]=min(st1[id],val);
return;
}
int mid=(l+r)>>1;
upd1(id<<1,l,mid,u,v,val);
upd1(id<<1|1,mid+1,r,u,v,val);
}
void upd2(int id,int l,int r,int u,int v,int val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
st2[id]=max(st2[id],val);
return;
}
int mid=(l+r)>>1;
upd2(id<<1,l,mid,u,v,val);
upd2(id<<1|1,mid+1,r,u,v,val);
}
pii get(int id,int l,int r,int u){
pii xxx={mx,mn};
while (true){
xxx.fi=min(xxx.fi,st1[id]);
xxx.se=max(xxx.se,st2[id]);
if (l==r)break;
int mid=(l+r)>>1;
if (mid>=u){
id=(id<<1);
r=mid;
}
else {
id=(id<<1|1);
l=mid+1;
}
}
return xxx;
}
void new_home(int id,int l,int r){
if (!st[id].empty()){
vector<int>cc;
for1(i,l,r){
for (auto v:answer[i]){
if (c[v]==-1)continue;
cc.pb(b[v].fi);
}
}
sort(all(cc));
cc.resize(distance(cc.begin(),unique(all(cc))));
if (!cc.empty()){
int m=sz(cc);
build(1,1,m);
for(auto v:st[id]){
int l1=v.fi,r1=v.se,mid=(l1+r1)/2;
l1=lower_bound(all(cc),l1)-cc.begin()+1;
r1=upper_bound(all(cc),r1)-cc.begin();
mid=upper_bound(all(cc),mid)-cc.begin();
upd1(1,1,m,l1,mid,v.fi);
upd2(1,1,m,mid+1,r1,v.se);
}
for1(i,l,r){
for (auto v:answer[i]){
if (c[v]==-1)continue;
int pos=lower_bound(all(cc),b[v].fi)-cc.begin()+1;
pii xxx=get(1,1,m,pos);
c[v]=max({c[v],b[v].fi-xxx.fi,xxx.se-b[v].fi});
}
}
}
}
if (l==r)return;
int mid=(l+r)>>1;
new_home(id<<1,l,mid);
new_home(id<<1|1,mid+1,r);
}
void init(){
    cin>>n>>k>>q;
    for1(i,1,n)cin>>a[i].x>>a[i].t>>a[i].a>>a[i].b;
    for1(i,1,q)cin>>b[i].fi>>b[i].se;
}
void nentime(){
    vector<int>tme;
    for1(i,1,q){
    tme.pb(b[i].se);
    }
    sort(all(tme));
    tme.resize(distance(tme.begin(),unique(all(tme))));
    for1(i,1,n){
    a[i].a=lower_bound(all(tme),a[i].a)-tme.begin()+1,a[i].b=upper_bound(all(tme),a[i].b)-tme.begin();
    if (a[i].a>a[i].b)continue;
    add[a[i].a].pb(i);
    del[a[i].b].pb(i);
    }
    for1(i,1,q){
    b[i].se=lower_bound(all(tme),b[i].se)-tme.begin()+1;
    answer[b[i].se].pb(i);
    }
    line=sz(tme);
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    init();
    nentime();
    for1(i,1,line){
    for (auto v:add[i]){
    add_point(a[v].x,a[v].t,i);
    }
    for (auto v:answer[i]){
    if (now<k){
    c[v]=-1;
    continue;
    }
    }
    for (auto v:del[i]){
    del_point(a[v].x,a[v].t,i+1);
    }
    }
    for1(i,1,k){
    for (auto u:temp[i]){
    update(1,1,line,u.tim,line,{u.l,u.r});
    }
    }
    new_home(1,1,line);
    for1(i,1,q)cout<<c[i]<<'\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20