Submission #1108444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108444		simona1230	New Home (APIO18_new_home)	C++17	12 / 100	5070 ms	48828 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;
}

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++)
    {
        int x,y;
        cin>>x>>y;
        v.push_back({x,i,y,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 main()
{
    read();
    solve();
    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:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<hour>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i=0; i<v.size(); 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