Submission #1112374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112374		Pioneer	New Home (APIO18_new_home)	C++17	0 / 100	5067 ms	313840 KiB

new_home

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

#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 ll inf=1e18;
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];
set<pii> st[MAX];
vector<int> tim,pos;

struct segtree{
    multiset<int> t[4*MAX];

    void add(int v,int tl,int tr,int l,int r,int x){
        if(l>r||tl>r||l>tr)return;
        if(l<=tl&&tr<=r){
            t[v].insert(x);
            return;
        }
        int tm=(tl+tr)/2;
        add(2*v,tl,tm,l,r,x);
        add(2*v+1,tm+1,tr,l,r,x);
    }

    void del(int v,int tl,int tr,int l,int r,int x){
        if(l>r||tl>r||l>tr)return;
        if(l<=tl&&tr<=r){
            t[v].erase(t[v].find(x));
            return;
        }
        int tm=(tl+tr)/2;
        del(2*v,tl,tm,l,r,x);
        del(2*v+1,tm+1,tr,l,r,x);
    }

    int get(int v,int tl,int tr,int p,int x){
        int res=0;
        if(!t[v].empty())res=max(abs(*t[v].begin()-x),abs(*t[v].rbegin()-x));
        // if(!t[v].empty())cout<<*t[v].begin()<<" "<<*t[v].rbegin()<<" "<<x<<"\n";
        if(tl==tr)return res;
        int tm=(tl+tr)/2;
        if(p<=tm)return max(res,get(2*v,tl,tm,p,x));
        else return max(res,get(2*v+1,tm+1,tr,p,x));
    }
}tree;

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

void add(int id){
    if(cnt[t[id]]==0)col++;
    cnt[t[id]]++;
    if(st[t[id]].empty()){
        L[id]=0,R[id]=m-1;
        tree.add(1,0,m-1,0,m-1,x[id]);
    }
    else{
        auto r=st[t[id]].lb({x[id],id});
        if(r==st[t[id]].end()){
            r--;
            tree.del(1,0,m-1,L[r->S],R[r->S],x[r->S]);
            int mid=ub(all(pos),(r->F+x[id])/2)-pos.begin()-1;
            R[r->S]=mid;
            L[id]=mid+1,R[id]=m-1;
            tree.add(1,0,m-1,L[r->S],R[r->S],x[r->S]);
            tree.add(1,0,m-1,L[id],R[id],x[id]);
        }
        else if(r==st[t[id]].begin()){
            tree.del(1,0,m-1,L[r->S],R[r->S],x[r->S]);
            int mid=ub(all(pos),(x[id]+r->F)/2)-pos.begin()-1;
            R[id]=mid,L[id]=0;
            L[r->S]=mid+1;
            tree.add(1,0,m-1,L[r->S],R[r->S],x[r->S]);
            tree.add(1,0,m-1,L[id],R[id],x[id]);
        }
        else{
            auto l=--st[t[id]].lb({x[id],id});
            tree.del(1,0,m-1,L[r->S],R[r->S],x[r->S]);
            tree.del(1,0,m-1,L[l->S],R[l->S],x[l->S]);
            int mid1=ub(all(pos),(x[id]+l->F)/2)-pos.begin()-1;
            int mid2=ub(all(pos),(x[id]+r->F)/2)-pos.begin()-1;
            R[l->S]=mid1;
            L[id]=mid1+1;
            R[id]=mid2;
            L[r->S]=mid2+1;
            tree.add(1,0,m-1,L[r->S],R[r->S],x[r->S]);
            tree.add(1,0,m-1,L[l->S],R[l->S],x[l->S]);
            tree.add(1,0,m-1,L[id],R[id],x[id]);
        }
    }
    st[t[id]].insert({x[id],id});
}

void del(int id){
    id=-id;
    cnt[t[id]]--;
    if(cnt[t[id]]==0)col--;
    if(sz(st[t[id]])==1){
        // cerr<<"OK\n";
        tree.del(1,0,m-1,0,m-1,x[id]);
    }
    else{
        tree.del(1,0,m-1,L[id],R[id],x[id]);
        auto r=st[t[id]].lb({x[id],id});
        if(r==st[t[id]].end()){
            r--;
            tree.del(1,0,m-1,L[r->S],R[r->S],x[r->S]);
            R[r->S]=m-1;
            tree.add(1,0,m-1,L[r->S],R[r->S],x[r->S]);
        }
        else if(r==st[t[id]].begin()){
            r++;
            tree.del(1,0,m-1,L[r->S],R[r->S],x[r->S]);
            L[r->S]=0;
            tree.add(1,0,m-1,L[r->S],R[r->S],x[r->S]);
        }
        else{
            auto l=--st[t[id]].lb({x[id],id});
            r++;
            tree.del(1,0,m-1,L[r->S],R[r->S],x[r->S]);
            tree.del(1,0,m-1,L[l->S],R[l->S],x[l->S]);
            int mid=ub(all(pos),(r->F+l->F)/2)-pos.begin()-1;
            R[l->S]=mid;
            L[id]=mid+1;
            tree.add(1,0,m-1,L[r->S],R[r->S],x[r->S]);
            tree.add(1,0,m-1,L[l->S],R[l->S],x[l->S]);
        }
    }
    st[t[id]].erase({x[id],id});
}

void solve(){
    cin>>n>>k>>q;
    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]);
    }
    for(int i=1;i<=q;i++){
        cin>>l[i]>>y[i];
        pos.pb(l[i]);
        tim.pb(y[i]);
    }
    sort(all(pos));
    pos.erase(unique(all(pos)),pos.end());
    sort(all(tim));
    tim.erase(unique(all(tim)),tim.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);
    }
    m=sz(pos);
    vector<int> ans(q+1,0);
    // cerr<<sz(tim)<<"\n";
    for(int i=0;i<sz(tim);i++){
        // cerr<<0<<"\n";
        for(auto id:events[i]){
            if(id>0){
                add(id);
            }
            else{
                del(id);
            }
        }
        // cout<<"! "<<tim[i]<<"\n";
        for(int id:zap[i]){
            // cout<<col<<"\n";
            // cout<<"? "<<id<<" "<<l[id]<<"\n";
            if(col!=k)ans[id]=-1;
            else ans[id]=tree.get(1,0,m-1,lb(all(pos),l[id])-pos.begin(),l[id]);
        }
        // for(int i=1;i<=n;i++)cout<<L[i]<<" "<<R[i]<<" "<<pos[L[i]]<<" "<<pos[R[i]]<<"\n";
    }
    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: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20