Submission #54034

#	Time	Username	Problem	Language	Result	Execution time	Memory
54034		bogdan10bos	New Home (APIO18_new_home)	C++14	12 / 100	5071 ms	44420 KiB

new_home

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef long long LL;

int N, K, Q;
LL sol[300005];

struct store
{
    int x, t, st, dr;

    store(int _x, int _t, int _st, int _dr) { x = _x, t = _t, st = _st, dr = _dr; }
};
vector<store> stores, ersStores;

struct query
{
    int x, tm, id;

    query(int _x, int _tm, int _id) { x = _x, tm = _tm, id = _id; }
};
vector<query> queries;

multiset<int> str[300005];

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d%d%d", &N, &K, &Q);

    for(int i = 1; i <= N; i++)
    {
        int x, t, st, dr;
        scanf("%d%d%d%d", &x, &t, &st, &dr);
        stores.push_back(store(x, t, st, dr));
    }
    ersStores = stores;
    sort(stores.begin(), stores.end(),
         [](store a, store b) { return a.st < b.st; });
    sort(ersStores.begin(), ersStores.end(),
         [](store a, store b) { return a.dr < b.dr; });

    for(int i = 1; i <= Q; i++)
    {
        int x, tm;
        scanf("%d%d", &x, &tm);
        queries.push_back(query(x, tm, i));
    }

    sort(queries.begin(), queries.end(),
         [](query a, query b) { return a.tm < b.tm; });

    int pi = 0;
    int pe = 0;
    for(auto &q: queries)
    {
        int pos = q.x;
        int t = q.tm;

        /// Insert stores
        while(pi < stores.size() && stores[pi].st <= t)
        {
            str[ stores[pi].t ].insert(stores[pi].x);
            pi++;
        }

        /// Erase stores
        while(pe < ersStores.size() && ersStores[pe].dr < t)
        {
            int tt = ersStores[pe].t;
            str[tt].erase( str[tt].find(ersStores[pe].x) );
            pe++;
        }

        /// Answer
        int ans = -1;
        for(int i = 1; i <= K; i++)
        {
            if(str[i].empty())
            {
                ans = -1;
                break;
            }

            auto it = str[i].lower_bound(pos);
            int mn = 1 << 30;
            if(it != str[i].end())  mn = abs((*it) - pos);
            if(it != str[i].begin())    it--;
            if(it != str[i].end())  mn = min(mn, abs((*it) - pos));

            ans = max(ans, mn);
        }
        sol[q.id] = ans;
    }

    for(int i = 1; i <= Q; i++)
        printf("%lld\n", sol[i]);

    return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:69:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(pi < stores.size() && stores[pi].st <= t)
               ~~~^~~~~~~~~~~~~~~
new_home.cpp:76:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(pe < ersStores.size() && ersStores[pe].dr < t)
               ~~~^~~~~~~~~~~~~~~~~~
new_home.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &K, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &x, &t, &st, &dr);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &tm);
         ~~~~~^~~~~~~~~~~~~~~~~

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