Submission #1108432

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1108432	2024-11-04T06:34:00 Z	simona1230	New Home (APIO18_new_home)	C++17	5 / 100	5000 ms	48820 KB

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
                {
                    int minn=1e9;
                    for(auto it=s[j].begin();it!=s[j].end();it++)
                    {
                        minn=min(minn,abs(h.x-*it));
                    }
                    maxx=max(maxx,minn);
                    /*auto it=s[j].begin();
                    if(h.x<*it)maxx=max(maxx,*it-h.x);
                    else
                    {
                        it=s[j].end();it--;
                        if(*it<=h.x)maxx=max(maxx,h.x-*it);
                        else
                        {
                            it=s[j].upper_bound(h.x);
                            maxx=max(maxx,h.x-*it);
                            it++;
                            maxx=max(maxx,*it-h.x);
                        }
                    }*/
                }
            }

            ans[h.t]=maxx;
        }
    }

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

int main()
{
    read();
    solve();
    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

new_home.cpp: In function 'void solve()':
new_home.cpp:65:18: 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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	16720 KB	Output is correct
2	Correct	3 ms	16720 KB	Output is correct
3	Correct	3 ms	16720 KB	Output is correct
4	Correct	3 ms	16832 KB	Output is correct
5	Correct	4 ms	16736 KB	Output is correct
6	Correct	4 ms	16848 KB	Output is correct
7	Correct	4 ms	16892 KB	Output is correct
8	Correct	4 ms	16720 KB	Output is correct
9	Correct	5 ms	16720 KB	Output is correct
10	Correct	4 ms	16720 KB	Output is correct
11	Correct	4 ms	16720 KB	Output is correct
12	Correct	4 ms	16720 KB	Output is correct
13	Correct	4 ms	16720 KB	Output is correct
14	Correct	4 ms	16888 KB	Output is correct
15	Correct	4 ms	16720 KB	Output is correct
16	Correct	4 ms	16720 KB	Output is correct
17	Correct	4 ms	16720 KB	Output is correct
18	Correct	4 ms	16720 KB	Output is correct
19	Correct	4 ms	16916 KB	Output is correct
20	Correct	4 ms	16720 KB	Output is correct
21	Correct	5 ms	16720 KB	Output is correct
22	Correct	4 ms	16720 KB	Output is correct
23	Correct	4 ms	16720 KB	Output is correct
24	Correct	4 ms	16720 KB	Output is correct
25	Correct	4 ms	16720 KB	Output is correct
26	Correct	4 ms	16720 KB	Output is correct
27	Correct	5 ms	16720 KB	Output is correct
28	Correct	5 ms	16720 KB	Output is correct
29	Correct	4 ms	16900 KB	Output is correct
30	Correct	5 ms	16888 KB	Output is correct

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	16720 KB	Output is correct
2	Correct	3 ms	16720 KB	Output is correct
3	Correct	3 ms	16720 KB	Output is correct
4	Correct	3 ms	16832 KB	Output is correct
5	Correct	4 ms	16736 KB	Output is correct
6	Correct	4 ms	16848 KB	Output is correct
7	Correct	4 ms	16892 KB	Output is correct
8	Correct	4 ms	16720 KB	Output is correct
9	Correct	5 ms	16720 KB	Output is correct
10	Correct	4 ms	16720 KB	Output is correct
11	Correct	4 ms	16720 KB	Output is correct
12	Correct	4 ms	16720 KB	Output is correct
13	Correct	4 ms	16720 KB	Output is correct
14	Correct	4 ms	16888 KB	Output is correct
15	Correct	4 ms	16720 KB	Output is correct
16	Correct	4 ms	16720 KB	Output is correct
17	Correct	4 ms	16720 KB	Output is correct
18	Correct	4 ms	16720 KB	Output is correct
19	Correct	4 ms	16916 KB	Output is correct
20	Correct	4 ms	16720 KB	Output is correct
21	Correct	5 ms	16720 KB	Output is correct
22	Correct	4 ms	16720 KB	Output is correct
23	Correct	4 ms	16720 KB	Output is correct
24	Correct	4 ms	16720 KB	Output is correct
25	Correct	4 ms	16720 KB	Output is correct
26	Correct	4 ms	16720 KB	Output is correct
27	Correct	5 ms	16720 KB	Output is correct
28	Correct	5 ms	16720 KB	Output is correct
29	Correct	4 ms	16900 KB	Output is correct
30	Correct	5 ms	16888 KB	Output is correct
31	Execution timed out	5051 ms	25372 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	5070 ms	48820 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	5021 ms	48776 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	16720 KB	Output is correct
2	Correct	3 ms	16720 KB	Output is correct
3	Correct	3 ms	16720 KB	Output is correct
4	Correct	3 ms	16832 KB	Output is correct
5	Correct	4 ms	16736 KB	Output is correct
6	Correct	4 ms	16848 KB	Output is correct
7	Correct	4 ms	16892 KB	Output is correct
8	Correct	4 ms	16720 KB	Output is correct
9	Correct	5 ms	16720 KB	Output is correct
10	Correct	4 ms	16720 KB	Output is correct
11	Correct	4 ms	16720 KB	Output is correct
12	Correct	4 ms	16720 KB	Output is correct
13	Correct	4 ms	16720 KB	Output is correct
14	Correct	4 ms	16888 KB	Output is correct
15	Correct	4 ms	16720 KB	Output is correct
16	Correct	4 ms	16720 KB	Output is correct
17	Correct	4 ms	16720 KB	Output is correct
18	Correct	4 ms	16720 KB	Output is correct
19	Correct	4 ms	16916 KB	Output is correct
20	Correct	4 ms	16720 KB	Output is correct
21	Correct	5 ms	16720 KB	Output is correct
22	Correct	4 ms	16720 KB	Output is correct
23	Correct	4 ms	16720 KB	Output is correct
24	Correct	4 ms	16720 KB	Output is correct
25	Correct	4 ms	16720 KB	Output is correct
26	Correct	4 ms	16720 KB	Output is correct
27	Correct	5 ms	16720 KB	Output is correct
28	Correct	5 ms	16720 KB	Output is correct
29	Correct	4 ms	16900 KB	Output is correct
30	Correct	5 ms	16888 KB	Output is correct
31	Execution timed out	5051 ms	25372 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	16720 KB	Output is correct
2	Correct	3 ms	16720 KB	Output is correct
3	Correct	3 ms	16720 KB	Output is correct
4	Correct	3 ms	16832 KB	Output is correct
5	Correct	4 ms	16736 KB	Output is correct
6	Correct	4 ms	16848 KB	Output is correct
7	Correct	4 ms	16892 KB	Output is correct
8	Correct	4 ms	16720 KB	Output is correct
9	Correct	5 ms	16720 KB	Output is correct
10	Correct	4 ms	16720 KB	Output is correct
11	Correct	4 ms	16720 KB	Output is correct
12	Correct	4 ms	16720 KB	Output is correct
13	Correct	4 ms	16720 KB	Output is correct
14	Correct	4 ms	16888 KB	Output is correct
15	Correct	4 ms	16720 KB	Output is correct
16	Correct	4 ms	16720 KB	Output is correct
17	Correct	4 ms	16720 KB	Output is correct
18	Correct	4 ms	16720 KB	Output is correct
19	Correct	4 ms	16916 KB	Output is correct
20	Correct	4 ms	16720 KB	Output is correct
21	Correct	5 ms	16720 KB	Output is correct
22	Correct	4 ms	16720 KB	Output is correct
23	Correct	4 ms	16720 KB	Output is correct
24	Correct	4 ms	16720 KB	Output is correct
25	Correct	4 ms	16720 KB	Output is correct
26	Correct	4 ms	16720 KB	Output is correct
27	Correct	5 ms	16720 KB	Output is correct
28	Correct	5 ms	16720 KB	Output is correct
29	Correct	4 ms	16900 KB	Output is correct
30	Correct	5 ms	16888 KB	Output is correct
31	Execution timed out	5051 ms	25372 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Submission #1108432

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 7.0

Subtask #3 0 / 10.0

Subtask #4 0 / 23.0

Subtask #5 0 / 35.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 7.0

Subtask #3
0 / 10.0

Subtask #4
0 / 23.0

Subtask #5
0 / 35.0

Subtask #6
0 / 20.0