Submission #1112498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112498		Pioneer	New Home (APIO18_new_home)	C++17	47 / 100	5069 ms	722608 KiB

new_home

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#define ll long long
// #define int ll
#define all(v) v.begin(),v.end()
#define sz(s) ((int)s.size())
#define pb push_back
#define F first
#define S second
#define pii pair<int,int>
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound

using namespace std;

const int inf=1e8;
const int MAX=3e5+10;
const int mod=1e9+7;

int binpow(int a,int n){
    if(!n)return 1;
    if(n%2==1)return a*binpow(a,n-1)%mod;
    int k=binpow(a,n/2);
    return k*k%mod;
}

int n,k,q,m;
int a[MAX],b[MAX],x[MAX],t[MAX];
int l[MAX],y[MAX];
vector<int> events[MAX+MAX],zap[MAX+MAX];
multiset<int> st[MAX];
vector<int> tim,pos;

struct segtree{
    multiset<int> t[4*8*MAX];
    int mx[4*8*MAX],L[4*8*MAX],R[4*8*MAX];
    int cnt=1;

    segtree(){
        memset(L,0,sizeof(L));
        memset(R,0,sizeof(R));
        memset(mx,-1,sizeof(mx));
    }

    void add(int v,int tl,int tr,int pos,int x){
        if(tl==tr){
            t[v].insert(x);
            mx[v]=*t[v].rbegin();
            // mx[v]=x;
            return;
        }
        int tm=(tl+tr)/2;
        if(pos<=tm){
            if(!L[v])L[v]=++cnt;
            add(L[v],tl,tm,pos,x);
        }
        else{
            if(!R[v])R[v]=++cnt;
            add(R[v],tm+1,tr,pos,x);
        }
        mx[v]=max(mx[L[v]],mx[R[v]]);
    }

    void del(int v,int tl,int tr,int pos,int x){
        if(tl==tr){
            t[v].erase(t[v].find(x));
            if(t[v].empty())mx[v]=-1;
            else mx[v]=*t[v].rbegin();
            return;
        }
        int tm=(tl+tr)/2;
        if(pos<=tm){
            del(L[v],tl,tm,pos,x);
        }
        else{
            del(R[v],tm+1,tr,pos,x);
        }
        mx[v]=max(mx[L[v]],mx[R[v]]);
    }

    int get(int v,int tl,int tr,int l,int r){
        if(l>r||tl>r||l>tr)return 0;
        if(l<=tl&&tr<=r)return mx[v];
        int tm=(tl+tr)/2;
        int res=0;
        if(L[v])res=max(res,get(L[v],tl,tm,l,r));
        if(R[v])res=max(res,get(R[v],tm+1,tr,l,r));
        return res;
    }
}tree;

int L[MAX],R[MAX];
int cnt[MAX],col;

int getx(int x){
    return lb(all(pos),x)-pos.begin();
}

void add(int id){
    if(cnt[t[id]]==0)col++;
    cnt[t[id]]++;
    if(st[t[id]].count(x[id]))st[t[id]].insert(x[id]);
    else{
        auto l=--st[t[id]].lb(x[id]);
        auto r=st[t[id]].lb(x[id]);
        if(!(*l==-1&&*r==inf+1))tree.del(1,0,m-1,getx(*l+1),*r-1);
        tree.add(1,0,m-1,getx(*l+1),x[id]-1);
        tree.add(1,0,m-1,getx(x[id]+1),*r-1);
        st[t[id]].insert(x[id]);
    }
}

void del(int id){
    id=-id;
    cnt[t[id]]--;
    if(cnt[t[id]]==0)col--;
    st[t[id]].erase(st[t[id]].find(x[id]));
    if(!st[t[id]].count(x[id])){
        auto l=--st[t[id]].lb(x[id]);
        auto r=st[t[id]].lb(x[id]);
        tree.del(1,0,m-1,getx(*l+1),x[id]-1);
        tree.del(1,0,m-1,getx(x[id]+1),*r-1);
        if(!(*l==-1&&*r==inf+1))tree.add(1,0,m-1,getx(*l+1),*r-1);
    }
}

bool check(int l,int r){
    l=max(l,0);
    r=min(r,inf);
    l=ub(all(pos),l)-pos.begin()-1;
    if(tree.get(1,0,m-1,0,l)>=r)return 0;
    return 1;
}

int ans[MAX];

void solve(){
    cin>>n>>k>>q;
    pos.pb(0),pos.pb(inf);
    for(int i=1;i<=n;i++){
        cin>>x[i]>>t[i]>>a[i]>>b[i];
        tim.pb(a[i]);
        tim.pb(b[i]+1);
        pos.pb(x[i]);
        pos.pb(x[i]+1);
        pos.pb(x[i]-1);
    }
    for(int i=1;i<=q;i++){
        cin>>l[i]>>y[i];
        tim.pb(y[i]);
    }
    sort(all(tim));
    tim.erase(unique(all(tim)),tim.end());
    sort(all(pos));
    pos.erase(unique(all(pos)),pos.end());
    for(int i=1;i<=n;i++){
        a[i]=lb(all(tim),a[i])-tim.begin();
        b[i]=lb(all(tim),b[i]+1)-tim.begin();
        events[a[i]].pb(i);
        events[b[i]].pb(-i);
    }
    for(int i=1;i<=q;i++){
        y[i]=lb(all(tim),y[i])-tim.begin();
        zap[y[i]].pb(i);
    }
    for(int i=1;i<=k;i++){
        st[i].insert(-1);
        st[i].insert(inf+1);
    }
    m=sz(pos);
    for(int i=0;i<sz(tim);i++){
        for(auto id:events[i]){
            if(id>0){
                add(id);
            }
            else{
                del(id);
            }
        }
        for(int id:zap[i]){
            if(col!=k){
                ans[id]=-1;
            }
            else{
                int L=0,R=inf,res=inf;
                while(L<=R){
                    int mid=(L+R)/2;
                    if(check(l[id]-mid,l[id]+mid)){
                        R=mid-1,res=mid;
                    }
                    else L=mid+1;
                }
                ans[id]=res;
            }
        }
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
}

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