Submission #976195

#	Time	Username	Problem	Language	Result	Execution time	Memory
976195		8pete8	New Home (APIO18_new_home)	C++17	0 / 100	583 ms	160760 KiB

new_home

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib> 
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
//#define int long long
//#define double long double
const int mxn=6e5,inf=1e9,minf=-1e9;
int mx;
int del[mxn+10];
set<int>pos[mxn+10];
int cnt=0;
int curid=0;
struct seg{
    priority_queue<pii,vector<pii>,greater<pii>>v[2*mxn+10];
    priority_queue<pii>v2[2*mxn+10];
    //v=-val v2=+val
    //keep max
    //val id
    void update(int l,int r,pii val,int type){//lazy on top, 1=right
        for(l+=mx,r+=mx;l<=r;l>>=1,r>>=1){
            if(l&1){
                if(type)v[l++].push(val);
                else v2[l++].push(val);
            }
            if(!(r&1)){
                if(type)v[r--].push(val);
                else v2[r--].push(val);
            }
        }
    }
    pii qry(int pos){
        pii ans={inf,minf};
        for(pos+=mx;pos>0;pos>>=1){
            while(!v[pos].empty()&&del[v[pos].top().s])v[pos].pop();
            if(v[pos].size())ans.f=min(ans.f,v[pos].top().f);
            while(!v2[pos].empty()&&del[v2[pos].top().s])v2[pos].pop();
            if(v2[pos].size())ans.s=max(ans.s,v2[pos].top().f);
        }
        return ans;
    }
}seg;
vector<int>comp;
int rangeleft[mxn+10],rangeright[mxn+10];
int rangeidleft[mxn+10],rangeidright[mxn+10];
int idpos[mxn+10],idposincomp[mxn+10];
int tmp;
void add(int x,int t){
    //x =pos in comp;
    auto it=pos[t].insert(x).f;
    if(it!=pos[t].begin()){
        it--;
        tmp=(*it);
        
        int val=(idpos[tmp]+idpos[x])/2;
        //find mid point
        auto it2=lb(all(comp),val)-comp.begin();
        /*
        if(it2==comp.size())assert(0);
        //find mid point in comp
        rangeright[tmp]=it2-1;
        rangeleft[x]=it2;
        del[rangeidright[tmp]]=1;
        rangeidright[tmp]=++curid;
        rangeidleft[x]=++curid;
        */
       // seg.update(idposincomp[tmp],rangeright[tmp],{-idpos[tmp],rangeidright[tmp]},1);
        it++;
    }
    else{
        rangeleft[x]=0;
        rangeidleft[x]=++curid;
    }
    it++;
    if(it!=pos[t].end()){
        tmp=(*it);
        /*
        int val=(idpos[tmp]+idpos[x])/2;
        auto it2=lb(all(comp),val)-comp.begin();
        if(it2==comp.size())assert(0);
        rangeright[x]=it2-1;
        rangeleft[tmp]=it2;
        del[rangeidleft[tmp]]=it2;
        rangeidright[x]=++curid;
        rangeidleft[tmp]=++curid;
        */
       // seg.update(rangeleft[tmp],idposincomp[tmp],{idpos[tmp],rangeidleft[tmp]},0);
    }
    else{
        rangeright[x]=comp.size()-1;
        rangeidright[x]=++curid;
    }
    //seg.update(rangeleft[x],idposincomp[x],{idpos[x],rangeidleft[x]},0);
  //  seg.update(idposincomp[x],rangeright[x],{-idpos[x],rangeidright[x]},1);
}
void die(int x,int t){
    return;
    del[rangeidleft[x]]=1;
    del[rangeidright[x]]=1;
    auto it=pos[t].find(x);
    if(it==pos[t].end())return;
    int l,r;
    if(it==pos[t].begin()){
        it++;
        if(it!=pos[t].end()){
            tmp=(*it);
            seg.update(0,rangeleft[tmp]-1,{idpos[tmp],rangeidleft[tmp]},0);
            rangeleft[tmp]=0;
        }
        it--;
        pos[t].erase(it);
        return;
    }
    it--;
    l=(*it);
    it++;
    it++;
    if(it==pos[t].end()){
        seg.update(rangeright[l]+1,mx,{-idpos[l],rangeidright[l]},1);
        rangeright[l]=mx;
        it--;
        pos[t].erase(it);
        return;
    }
    else r=(*it);
    int val=(idpos[l]+idpos[r])/2;
    auto it2=lb(all(comp),val)-comp.begin();
    seg.update(rangeright[l],val-1,{-idpos[l],rangeidright[l]},1);
    seg.update(val,rangeleft[r],{idpos[r],rangeidleft[r]},0);
    rangeright[l]=val-1;
    rangeleft[r]=val;
    it--;
    pos[t].erase(it);
    return;
}
int ans[mxn+10];
struct info{int time,etype,pos,type,id;};
bool cmp(info a,info b){return a.pos<b.pos;}
bool cmp2(info a,info b){
    if(a.time==b.time)return a.etype<b.etype;
    return a.time<b.time;
}
vector<info>event;
int what[mxn+10];
int32_t main(){
    fastio
    int n,k,q;cin>>n>>k>>q;
    for(int i=0;i<n;i++){
        int x,t,a,b;cin>>x>>t>>a>>b;
        event.pb({a,1,x,t,i});
        event.pb({b+1,0,x,t,i});
        comp.pb(x);
    }
    vector<pair<pii,int>>qry(q);
    for(int i=0;i<q;i++)cin>>qry[i].f.s>>qry[i].f.f,qry[i].s=i,comp.pb(qry[i].s);
    sort(all(qry));
    sort(all(event),cmp);
    sort(all(comp));
    comp.erase(unique(all(comp)),comp.end());
    int cnt=0;
    for(auto &i:event){
        if(i.etype==0){
            i.id=what[i.id];
            continue;
        }
        what[i.id]=cnt;
        i.id=cnt;
        idpos[cnt]=i.pos;
        idposincomp[cnt]=lb(all(comp),i.pos)-comp.begin();
        cnt++;
    }
    sort(all(event),cmp2);
    mx=comp.size();
    int cur=0;
    cnt=0;
    for(auto i:qry){
        while(cur<event.size()&&event[cur].time<=i.f.f){
            //cout<<event[cur].time<<" "<<event[cur].type<<" "<<event[cur].pos<<' '<<event[cur].etype<<'\n';
            if(event[cur].etype){
                if(pos[event[cur].type].size()==0)cnt++;
                add(event[cur].id,event[cur].type);
            }
            else {
                die(event[cur].id,event[cur].type);
                if(pos[event[cur].type].size()==0)cnt--;
            }
            cur++;
        }
        pii bru=seg.qry(lb(all(comp),i.f.s)-comp.begin());
        if(cnt!=k)ans[i.s]=-1;
        else ans[i.s]=max(i.f.s+bru.f,bru.s-i.f.s);
    }
    for(int i=0;i<q;i++)cout<<ans[i]<<'\n';
	return 0;
}

/*
(2*n+q)log(n)*log(10^8)
when there are currently a,b,c shop active with the same k
int range of each shop will be (0,(a+b)/2),((a+b)/2+1,(b+c)/2),((b+c)/2+1,mx)
the contribution on range l,r when shop pos is x will be
x-a,x-b,x,c-x,d-x;
we can keep muliset segtree

*/

Compilation message (stderr)

new_home.cpp: In function 'void add(int, int)':
new_home.cpp:88:14: warning: unused variable 'it2' [-Wunused-variable]
   88 |         auto it2=lb(all(comp),val)-comp.begin();
      |              ^~~
new_home.cpp: In function 'void die(int, int)':
new_home.cpp:158:10: warning: unused variable 'it2' [-Wunused-variable]
  158 |     auto it2=lb(all(comp),val)-comp.begin();
      |          ^~~
new_home.cpp: In function 'int32_t main()':
new_home.cpp:208:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  208 |         while(cur<event.size()&&event[cur].time<=i.f.f){
      |               ~~~^~~~~~~~~~~~~

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