Submission #698808

#	Time	Username	Problem	Language	Result	Execution time	Memory
698808		vjudge1	New Home (APIO18_new_home)	C++17	12 / 100	5081 ms	279948 KiB

new_home

#include<bits/stdc++.h>
#define maxn 550000
#define maxl 8000000
#define bl 1000
using namespace std;
int n,k,q;
int x[maxn];
int a[maxn];
int b[maxn];
int t[maxn];
int l[maxn];
int y[maxn];
int ap[maxn];
bool fn[maxn];
int ans[maxn];
vector<pair<pair<int,int>,int> > v;
vector<pair<int,int> > c;
vector<int> cs;
bool cur[maxn];
int segp[4*maxl];
int segm[4*maxl];
int lc[4*maxl];
int rc[4*maxl];
int ord[4*maxn];
multiset<int> ns[2*bl];
int cnt=1;
void clear_seg() {
    cnt=1;
    segp[0]=-1e8;
    segm[0]=0;
    lc[0]=rc[0]=0;
}
inline void create_children(int id,int l,int r) {
    if(lc[id]==0) {
        segp[cnt]=-1e8;
        segm[cnt]=0;
        lc[cnt]=rc[cnt]=0;
        lc[id]=cnt++;
    }
    if(rc[id]==0) {
        segp[cnt]=-1e8;
        segm[cnt]=0;
        lc[cnt]=rc[cnt]=0;
        rc[id]=cnt++;
    }
}
void update(int id,int l,int r,int p,int q,int a,int b) {
    int m=(l+r)/2;
    create_children(id,l,r);
    if(p<=l && r<=q) {
        if(b==1) segp[id]=max(segp[id],a+l-1);
        else segm[id]=max(segm[id],a+1-l);
        return;
    }
    if(q<l || r<p) {
        return;
    }
    update(lc[id],l,m,p,q,a,b);
    update(rc[id],m+1,r,p,q,a,b);
}
int dif(int id,int l,int r,int x) {
    if(id==0 && !(l==1 && r==1e8)) return 0;
    int cur=max(segp[id]+x-l,segm[id]+l-x);
    int m=(l+r)/2;
    if(x<=m) return max(cur,dif(lc[id],l,m,x));
    else  return max(cur,dif(rc[id],m+1,r,x));
}
int main() {
    scanf("%d %d %d",&n,&k,&q);
    for(int i=1;i<=n;i++) {
        scanf("%d %d %d %d",&x[i],&t[i],&a[i],&b[i]);
        v.push_back({{a[i],0},i});
        v.push_back({{b[i],2},i});
    }
    for(int i=1;i<=q;i++) {
        scanf("%d %d",&l[i],&y[i]);
        v.push_back({{y[i],1},n+i});
    }
    sort(v.begin(),v.end());
    /*for(int i=0;i<v.size();i++) {
        cout<<v[i].first.first<<" "<<v[i].first.second<<" "<<v[i].second<<endl;
    }*/
    for(int i=0;i<v.size();i+=bl) {
        int cnt=0;
        for(int j=i;j<v.size() && j<i+bl;j++) {
            int ind=v[j].second;
            if(ind<=n) {
                if(ap[t[ind]]==0) {
                    cur[t[ind]]=true;
                    ord[t[ind]]=cnt;
                    cs.push_back(cnt);
                    cnt++;
                }
                ap[t[ind]]++;
            }
        }
        for(int j=i-1;j>=0;j--) {
            int ind=v[j].second;
            if(ind<=n) {
                if(v[j].first.second==2) fn[ind]=true;
                else {
                    if(!fn[ind] && ap[t[ind]]==0) {
                        c.push_back({t[ind],x[ind]});
                    }
                }
            }
        }
        for(int j=i-1;j>=0;j--) {
            int ind=v[j].second;
            if(ind<=n) {
                if(v[j].first.second==2) fn[ind]=true;
                else {
                    if(!fn[ind] && ap[t[ind]]==0) {
                        if(ap[t[ind]]==0) cnt++;
                        ap[t[ind]]++;
                    }
                }
            }
        }
        if(cnt==k) {
            sort(c.begin(),c.end());
            clear_seg();
            for(int i=0;i<c.size();i++) {
                if(i==0 || c[i-1].first!=c[i].first) {
                    update(0,1,1e8,1,c[i].second,c[i].second-1,-1);
                }
                else {
                    update(0,1,1e8,(c[i].second+c[i-1].second+1)/2,c[i].second,c[i].second-1,-1);
                }
                if(i+1==c.size() || c[i+1].first!=c[i].first) {
                    update(0,1,1e8,c[i].second,1e8,1-c[i].second,1);
                }
                else {
                    update(0,1,1e8,c[i].second,(c[i].second+c[i+1].second)/2,1-c[i].second,1);
                }
            }

            for(int j=i-1;j>=0;j--) {
                int ind=v[j].second;
                if(ind<=n) {
                    if(v[j].first.second==2) fn[ind]=true;
                    else {
                        if(!fn[ind] && cur[t[ind]]) {
                            ns[ord[t[ind]]].insert(x[ind]);
                        }
                    }
                }
            }

            for(int j=i;j<v.size() && j<i+bl;j++) {
                int ind=v[j].second;
                if(ind<=n) {
                    //cout<<j<<" "<<ind<<" "<<ord[t[ind]]<<" "<<v[j].first.second<<endl;
                    if(v[j].first.second==2) ns[ord[t[ind]]].erase(ns[ord[t[ind]]].find(x[ind]));
                    else ns[ord[t[ind]]].insert(x[ind]);
                }
                else {
                    ind-=n;
                    //cout<<j<<" "<<ind<<" "<<v[j].first.second<<endl;
                    for(auto tip:cs) {
                        //cout<<"\t"<<tip<<" "<<ns[tip].size()<<endl;
                        if(ns[tip].size()==0) ans[ind]=-1;
                    }
                    if(ans[ind]!=-1) {
                        if(cnt==cs.size()) ans[ind]=0;
                        else ans[ind]=dif(0,1,1e8,l[ind]);
                        for(auto tip:cs) {
                            set<int>::iterator it=ns[tip].lower_bound(l[ind]);
                            //cout<<l[ind]<<" "<<(*it)<<endl;
                            int csur=1e8;
                            if(it!=ns[tip].end()) csur=min(csur,(*it)-l[ind]);
                            if(it!=ns[tip].begin()) {
                                it--;
                                csur=min(csur,l[ind]-(*it));
                            }
                            ans[ind]=max(ans[ind],csur);
                        }
                    }
                }
            }

        }
        else {
            for(int j=i;j<v.size() && j<i+bl;j++) {
                int ind=v[j].second;
                if(ind>n) {
                    ans[ind-n]=-1;
                }
            }
        }
        c.clear();
        for(int j=0;j<v.size() && j<i+bl;j++) {
            int ind=v[j].second;
            if(ind<=n) {
                cur[t[ind]]=false;
                ns[ord[t[ind]]].clear();
                ord[t[ind]]=0;
                ap[t[ind]]=0;
            }
        }
        cs.clear();
    }
    for(int j=1;j<=q;j++) printf("%d\n",ans[j]);
    return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i=0;i<v.size();i+=bl) {
      |                 ~^~~~~~~~~
new_home.cpp:85:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(int j=i;j<v.size() && j<i+bl;j++) {
      |                     ~^~~~~~~~~
new_home.cpp:123:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |             for(int i=0;i<c.size();i++) {
      |                         ~^~~~~~~~~
new_home.cpp:130:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |                 if(i+1==c.size() || c[i+1].first!=c[i].first) {
      |                    ~~~^~~~~~~~~~
new_home.cpp:150:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |             for(int j=i;j<v.size() && j<i+bl;j++) {
      |                         ~^~~~~~~~~
new_home.cpp:165:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |                         if(cnt==cs.size()) ans[ind]=0;
      |                            ~~~^~~~~~~~~~~
new_home.cpp:184:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |             for(int j=i;j<v.size() && j<i+bl;j++) {
      |                         ~^~~~~~~~~
new_home.cpp:192:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |         for(int j=0;j<v.size() && j<i+bl;j++) {
      |                     ~^~~~~~~~~
new_home.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     scanf("%d %d %d",&n,&k,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
new_home.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf("%d %d %d %d",&x[i],&t[i],&a[i],&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf("%d %d",&l[i],&y[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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