oj.uz

Submission #1108440

# Submission time Handle Problem Language Result Execution time Memory
1108440 2024-11-04T06:59:19 Z simona1230 New Home (APIO18_new_home) C++17
0 / 100
 5000 ms 48832 KB 
#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);
                        //cout<<"! "<<j<<" "<<*it<<" "<<h.x<<endl;
                        maxx=max(maxx,*it-h.x);
                        if(it!=s[j].begin())
                        {
                            it--;
                            maxx=max(maxx,h.x-*it);
                        }
                    }
                }
            }

            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

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16720 KB Output is correct
2 Correct 4 ms 16720 KB Output is correct
3 Correct 3 ms 16720 KB Output is correct
4 Incorrect 4 ms 16720 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16720 KB Output is correct
2 Correct 4 ms 16720 KB Output is correct
3 Correct 3 ms 16720 KB Output is correct
4 Incorrect 4 ms 16720 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5063 ms 48832 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 5058 ms 48708 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 4 ms 16720 KB Output is correct
3 Correct 3 ms 16720 KB Output is correct
4 Incorrect 4 ms 16720 KB Output isn't correct
5 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 4 ms 16720 KB Output is correct
3 Correct 3 ms 16720 KB Output is correct
4 Incorrect 4 ms 16720 KB Output isn't correct
5 Halted 0 ms 0 KB -