Submission #1088704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088704		alexander707070	New Home (APIO18_new_home)	C++14	47 / 100	3308 ms	1023768 KiB

new_home

#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#define MAXN 3000007
using namespace std;

const int inf=1e9+7;

int n,k,q,x,t,l,r,ans[MAXN];

struct event{
    int x,type,tim,id;

    inline friend bool operator < (event fr,event sc){
        if(fr.tim!=sc.tim)return fr.tim<sc.tim;
        else return fr.type<sc.type;
    }
}s[MAXN];

multiset<int> stores[MAXN];

/*void solve(){

    tim++; ask.clear();
    for(event e:z){
        if((e.type==0 or e.type==2) and false){
            sp[e.id]=tim;
        }else if(e.type==1){
            ask.push_back(e);
        }
    }

    poss.clear(); st.clear(); ts.clear();
    for(int i=1;i<=k;i++){
        if(sp[i]==tim)poss.push_back(i);
        else{
            vector<int> w;
            for(int f:stores[i]){
                w.push_back(f);
            }

            if(w.empty()){
                st.push_back({0,inf});
                ts.push_back({inf,2*inf});
                break;
            }

            st.push_back({0,w[0]});
            for(int f=0;f<w.size()-1;f++){
                int pos=(w[f]+w[f+1])/2+(w[f]+w[f+1])%2;
                int val=(w[f+1]-w[f])/2;

                st.push_back({pos,pos+val});
                ts.push_back({pos-(w[f]+w[f+1])%2,val-(pos-(w[f]+w[f+1])%2)});
            }
            ts.push_back({inf,-w.back()});
        }
    }

    if(!st.empty()){
        sort(st.begin(),st.end());
        sort(ts.begin(),ts.end());
        sort(ask.begin(),ask.end(),cmp);

        int pt=0;
        while(!pq.empty())pq.pop();

        for(int i=0;i<ask.size();i++){
            while(pt<st.size() and st[pt].first<=ask[i].x){
                pq.push(st[pt].second);
                pt++;
            }

            ans[ask[i].id]=max(ans[ask[i].id],pq.top()-ask[i].x);
        }

        pt=ts.size()-1;
        while(!pq.empty())pq.pop();

        for(int i=ask.size()-1;i>=0;i--){
            while(pt>=0 and ts[pt].first>=ask[i].x){
                pq.push(ts[pt].second);
                pt--;
            }

            ans[ask[i].id]=max(ans[ask[i].id],pq.top()+ask[i].x);
        }
    }

    for(event e:z){
        if(e.type==0){
            stores[e.id].insert(e.x);
        }else if(e.type==2){
            stores[e.id].erase(stores[e.id].find(e.x));
        }else{
            for(int i:poss){
                ans[e.id]=max(ans[e.id],calc(e.x,i));
            }
        }
    }
}*/

struct node{
    int l,r;
    int val;
    int setid;
};

int num,pt,ft;
node tree[4*MAXN];
multiset<int> vals[MAXN];

void update(int v,int l,int r,int pos,int val,bool t){
    if(l==r){
        if(tree[v].setid==0){
            ft++; tree[v].setid=ft;
        }

        int id=tree[v].setid;

        if(t)vals[id].insert(val);
        else vals[id].erase(vals[id].find(val));

        if(!vals[id].empty())tree[v].val=*vals[id].rbegin();
        else tree[v].val=-inf;
    }else{
        int tt=(l+r)/2;

        if(tree[v].l==0){
            num++; tree[v].l=num;
            tree[num].val=-inf;
        }
        if(tree[v].r==0){
            num++; tree[v].r=num;
            tree[num].val=-inf;
        }

        if(pos<=tt)update(tree[v].l,l,tt,pos,val,t);
        else update(tree[v].r,tt+1,r,pos,val,t);

        tree[v].val=max(tree[tree[v].l].val,tree[tree[v].r].val);
    }
}

int getmax(int v,int l,int r,int ll,int rr){
    if(ll>rr or v==0)return -inf;

    if(l==ll and r==rr){
        return tree[v].val;
    }else{
        int tt=(l+r)/2;
        return max( getmax(tree[v].l,l,tt,ll,min(tt,rr)) , getmax(tree[v].r,tt+1,r,max(tt+1,ll),rr) );
    }
}

void addline(int pos,int val){
    update(1,0,inf,pos,val,true);
}

void remline(int pos,int val){
    update(1,0,inf,pos,val,false);
}

int up(int s){
    if(s>=0)return s/2+s%2;
    else return s/2;
}

int down(int s){
    if(s>=0)return s/2;
    else return s/2+s%2;
}

void add(int x,int type,bool dir){
    stores[type].insert(x);
    auto it=stores[type].find(x);

    it--;
    int lpos=*it;
    it++; it++;
    int rpos=*it;

    if(!dir){
        remline(up(lpos+rpos),(rpos-lpos)/2+up(lpos+rpos));
        addline(up(lpos+x),(x-lpos)/2+up(lpos+x));
        addline(up(x+rpos),(rpos-x)/2+up(x+rpos));
    }else{
        remline(down(lpos+rpos),(rpos-lpos)/2-down(lpos+rpos));
        addline(down(lpos+x),(x-lpos)/2-down(lpos+x));
        addline(down(x+rpos),(rpos-x)/2-down(x+rpos));
    }
}

void rem(int x,int type,bool dir){
    auto it=stores[type].find(x);

    it--;
    int lpos=*it;
    it++; it++;
    int rpos=*it;

    if(!dir){
        addline(up(lpos+rpos),(rpos-lpos)/2+up(lpos+rpos));
        remline(up(lpos+x),(x-lpos)/2+up(lpos+x));
        remline(up(x+rpos),(rpos-x)/2+up(x+rpos));
    }else{
        addline(down(lpos+rpos),(rpos-lpos)/2-down(lpos+rpos));
        remline(down(lpos+x),(x-lpos)/2-down(lpos+x));
        remline(down(x+rpos),(rpos-x)/2-down(x+rpos));
    }

    stores[type].erase(stores[type].find(x));
}

int maxs(int l,int r){
    return getmax(1,0,inf,l,r);
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>k>>q;

    for(int i=1;i<=k;i++){
        stores[i].insert(0);
        stores[i].insert(inf);
    }

    for(int i=1;i<=n;i++){
        cin>>x>>t>>l>>r;
        x+=inf/2;

        pt++; s[pt]={x,0,l,t};
        pt++; s[pt]={x,2,r,t};
    }

    for(int i=1;i<=q;i++){
        cin>>x>>t;
        x+=inf/2;

        pt++; s[pt]={x,1,t,i};
    }

    sort(s+1,s+pt+1);

    num=1;
    for(int i=1;i<=k;i++)addline(up(0+inf),inf/2+up(0+inf));
    
    for(int i=1;i<=pt;i++){
        if(s[i].type==0){
            add(s[i].x,s[i].id,false);
        }else if(s[i].type==2){
            rem(s[i].x,s[i].id,false);
        }else{
            ans[s[i].id]=max(ans[s[i].id],maxs(0,s[i].x)-s[i].x);
        }
    }
    
    for(int i=1;i<=k;i++){
        remline(up(0+inf),inf/2+up(0+inf));
        addline(down(0+inf),inf/2-down(0+inf));
    }

    for(int i=1;i<=pt;i++){
        if(s[i].type==0){
            add(s[i].x,s[i].id,true);
        }else if(s[i].type==2){
            rem(s[i].x,s[i].id,true);
        }else{
            ans[s[i].id]=max(ans[s[i].id],maxs(s[i].x,inf)+s[i].x);
        }
    }

    for(int i=1;i<=q;i++){
        if(ans[i]>200000000)cout<<"-1\n";
        else cout<<ans[i]<<"\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

*/

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