Submission #1108854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108854		simona1230	New Home (APIO18_new_home)	C++17	5 / 100	1125 ms	52560 KiB

new_home

#include <bits/stdc++.h>
using namespace std;

struct store
{
    int x,t,a,b;
    store() {}
    store(int _x,int _t,int _a,int _b)
    {
        x=_x;
        t=_t;
        a=_a;
        b=_b;
    }
};

struct hour
{
    int x,t,h,p;
    hour() {}
    hour(int _x,int _t,int _h,int _p)
    {
        x=_x;
        t=_t;
        h=_h;
        p=_p;
    }
};

int n,q,k;
store a[300001];
multiset<int> s[300001];
vector<hour> v;

bool cmp(hour h1,hour h2)
{
    if(h1.h==h2.h)return h1.p<h2.p;
    return h1.h<h2.h;
}

int x[300001],y[300001];

void read()
{
    cin>>n>>k>>q;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i].x>>a[i].t>>a[i].a>>a[i].b;
        v.push_back({a[i].x,a[i].t,a[i].a,1});
        v.push_back({a[i].x,a[i].t,a[i].b,3});
    }

    for(int i=1; i<=q; i++)
    {
        cin>>x[i]>>y[i];
        v.push_back({x[i],i,y[i],2});
    }

    sort(v.begin(),v.end(),cmp);
}

int ans[300001];

void solve()
{
    for(int i=0; i<v.size(); i++)
    {
        hour h=v[i];
        //cout<<h.x<<" "<<h.t<<" "<<h.p<<" "<<h.h<<endl;
        if(h.p==1)s[h.t].insert(h.x);
        else if(h.p==3)s[h.t].erase(s[h.t].find(h.x));
        else
        {
            int maxx=0;
            for(int j=1; j<=k; j++)
            {
                if(s[j].size()==0)
                {
                    maxx=-1;
                    break;
                }
                else
                {
                    auto it=s[j].end();it--;
                    //cout<<"! "<<j<<" "<<*it<<endl;
                    if(h.x>=*it)maxx=max(maxx,h.x-*it);
                    else
                    {
                        it=s[j].lower_bound(h.x);
                        int d=*it-h.x;
                        //cout<<"! "<<j<<" "<<*it<<" "<<h.x<<endl;
                        if(it!=s[j].begin())
                        {
                            it--;
                            d=min(d,h.x-*it);
                        }

                        maxx=max(maxx,d);
                    }
                }
            }

            ans[h.t]=maxx;
        }
    }

    for(int i=1; i<=q; i++)
        cout<<ans[i]<<endl;
}

int last[300001];
set<int> act;

struct position
{
    int x,t;
    position(){}
    position(int _x,int _t)
    {
        x=_x;
        t=_t;
    }
};

bool cmp2(position p1,position p2)
{
    return p1.x<p2.x;
}

void subt()
{
    vector<position> p;
    for(int i=1;i<=n;i++)
    {
        p.push_back({a[i].x,a[i].t});
    }

    for(int i=1;i<=q;i++)
    {
        p.push_back({x[i],-i});
    }

    sort(p.begin(),p.end(),cmp2);

    for(int i=0;i<p.size();i++)
    {
        if(p[i].t<0)
        {
            int id=p[i].t;
            if(act.size()==0)ans[id]=-1;
            else
            {
                auto it=act.end();
                it--;

                ans[id]=p[i].x-*it;
            }
        }
        else
        {
            if(last[p[i].t])act.erase(last[p[i].t]);
            last[p[i].t]=p[i].x;
            act.insert(p[i].x);
        }
    }

    for(int i=1;i<=k;i++)
        last[i]=-1;

    for(int i=p.size()-1;i>=0;i--)
    {
        if(p[i].t<0)
        {
            int id=p[i].t;
            if(act.size()==0)ans[id]=-1;
            else
            {
                auto it=act.begin();
                if(ans[id]==-1||ans[id]>*it-p[i].x)
                    ans[id]=p[i].x-*it;
            }
        }
        else
        {
            if(last[p[i].t])act.erase(last[p[i].t]);
            last[p[i].t]=p[i].x;
            act.insert(p[i].x);
        }
    }

    for(int i=1;i<=n;i++)
        cout<<ans[i]<<endl;
}

int main()
{
    read();
    if(n<=4*10000)solve();
    else subt();
    return 0;
}

/*
4 2 1
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
9 4
*/

Compilation message (stderr)

new_home.cpp: In function 'void solve()':
new_home.cpp:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<hour>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i=0; i<v.size(); i++)
      |                  ~^~~~~~~~~
new_home.cpp: In function 'void subt()':
new_home.cpp:145:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<position>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for(int i=0;i<p.size();i++)
      |                 ~^~~~~~~~~
new_home.cpp:179:26: warning: array subscript -1 is below array bounds of 'int [300001]' [-Warray-bounds]
  179 |                 if(ans[id]==-1||ans[id]>*it-p[i].x)
      |                    ~~~~~~^
new_home.cpp:62:5: note: while referencing 'ans'
   62 | int ans[300001];
      |     ^~~
new_home.cpp:180:27: warning: array subscript -1 is below array bounds of 'int [300001]' [-Warray-bounds]
  180 |                     ans[id]=p[i].x-*it;
      |                     ~~~~~~^
new_home.cpp:62:5: note: while referencing 'ans'
   62 | int ans[300001];
      |     ^~~
new_home.cpp:175:36: warning: array subscript -1 is below array bounds of 'int [300001]' [-Warray-bounds]
  175 |             if(act.size()==0)ans[id]=-1;
      |                              ~~~~~~^
new_home.cpp:62:5: note: while referencing 'ans'
   62 | int ans[300001];
      |     ^~~
new_home.cpp:156:23: warning: array subscript -1 is below array bounds of 'int [300001]' [-Warray-bounds]
  156 |                 ans[id]=p[i].x-*it;
      |                 ~~~~~~^
new_home.cpp:62:5: note: while referencing 'ans'
   62 | int ans[300001];
      |     ^~~
new_home.cpp:150:36: warning: array subscript -1 is below array bounds of 'int [300001]' [-Warray-bounds]
  150 |             if(act.size()==0)ans[id]=-1;
      |                              ~~~~~~^
new_home.cpp:62:5: note: while referencing 'ans'
   62 | int ans[300001];
      |     ^~~

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