Submission #1088680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088680		alexander707070	New Home (APIO18_new_home)	C++14	12 / 100	5090 ms	103584 KiB

new_home

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

#define MAXN 1000007
using namespace std;

const int bucket_sz=1000007,inf=1e9+7;

int n,k,q,x,t,l,r,pt,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];

bool cmp(event fr,event sc){
    return fr.x<sc.x;
}

multiset<int> stores[MAXN];
set< pair<int,int> > ss;
vector< pair<int,int> > st,ts;

vector<event> z,ask;

int sp[MAXN],tim;
vector<int> poss;
priority_queue<int> pq;

int mins(){
    pair<int,int> p=*ss.begin();
    return p.first;
}

int maxs(){
    pair<int,int> p=*ss.rbegin();
    return p.first;
}

int calc(int x,int t){
    if(stores[t].empty())return inf;

    auto it=stores[t].lower_bound(x);

    int p1=-inf,p2=-inf;

    if(it!=stores[t].end())p1=*it;
    if(it!=stores[t].begin()){
        it--; p2=*it;
    }

    return min(abs(x-p1),abs(x-p2));
}

void solve(){

    tim++; ask.clear();
    for(event e:z){
        if(e.type==0 or e.type==2){
            sp[e.id]=tim;
        }else{
            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));
            }
        }
    }
}

int main(){

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

    cin>>n>>k>>q;
    for(int i=1;i<=n;i++){
        cin>>x>>t>>l>>r;

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

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

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

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

    for(int i=1;i<=pt;i++){
        z.push_back(s[i]);

        if(z.size()==bucket_sz){
            solve(); z.clear();
        }
    }

    if(!z.empty()){
        solve(); z.clear();
    }

    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

*/

Compilation message (stderr)

new_home.cpp: In function 'void solve()':
new_home.cpp:87:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |             for(int f=0;f<w.size()-1;f++){
      |                         ~^~~~~~~~~~~
new_home.cpp:106:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(int i=0;i<ask.size();i++){
      |                     ~^~~~~~~~~~~
new_home.cpp:107:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |             while(pt<st.size() and st[pt].first<=ask[i].x){
      |                   ~~^~~~~~~~~~

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