Submission #218057

#	Time	Username	Problem	Language	Result	Execution time	Memory
218057		Vimmer	New Home (APIO18_new_home)	C++14	22 / 100	2766 ms	51220 KiB

new_home

#include <bits/stdc++.h>

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 300005
#define M ll(998244353)

using namespace std;

typedef long double ld;
typedef long long ll;
typedef short int si;


vector <pair <pair <pair <int, int>, int>, int> > sost;

set <int> se[410];

map <pair <int, int>, int > mp;

vector <pair <int, int> > vr;

vector <int> qr[N];

int pos[N];

int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, k, q;

    cin >> n >> k >> q;

    if (n <= 60000)
    {
        for (int i = 0; i < n; i++)
        {
            int x, t, l, r;

            cin >> x >> t >> l >> r;

            sost.pb({{{l, x}, t}, i});

            sost.pb({{{r + 1, x}, -t}, i});
        }

        vector <pair <pair <int, int>, int>  > gr; gr.resize(q);

        for (int i = 0; i < q; i++) {cin >> gr[i].F.S >> gr[i].F.F; gr[i].S = i;}

        sort(sost.begin(), sost.end());

        sort(gr.begin(), gr.end());

        int ans[q];

        int j = 0;

        for (auto it : gr)
        {
            int nm = it.S, x = it.F.S, tr = it.F.F;

            while (j < n + n && sost[j].F.F.F <= tr)
            {
                int tp = abs(sost[j].F.S);

                if (sost[j].F.S > 0) {mp[{tp, sost[j].F.F.S}]++; if (mp[{tp, sost[j].F.F.S}] == 1) se[tp].insert(sost[j].F.F.S);}
                   else  {mp[{tp, sost[j].F.F.S}]--; if (mp[{tp, sost[j].F.F.S}] == 0) se[tp].erase(sost[j].F.F.S);}

                j++;
            }

            bool f = 1;

            int mx = 0;

            for (int i = 1; i <= k; i++)
            {
                if (sz(se[i]) == 0) {f = 0; break;}

                auto it = se[i].lower_bound(x);

                int mn = 1e9;

                if (it != se[i].end()) mn = min(mn, abs(*it - x));

                if (it != se[i].begin()) {it--; mn = min(mn, abs(*it - x)); }

                mx = max(mx, mn);
            }

            if (!f) ans[nm] = -1; else ans[nm] = mx;
        }

        for (int i = 0; i < q; i++) cout << ans[i] << endl;
    }
    else
    {
        for (int i = 0; i < n; i++)
        {
            int x, t, a, b;

            cin >> x >> t >> a >> b;

            qr[t].pb(x);
        }

        set <pair <int, int> > se; se.clear();

        for (int i = 1; i <= k; i++) sort(qr[i].begin(), qr[i].end());

        bool f = 1;

        for (int i = 1; i <= k; i++)
        {
            if (sz(qr[i]) == 0) {f = 0; break;}

            se.insert({qr[i][0], i});

            int lst = qr[i][0];

            for (int j = 1; j < sz(qr[i]); j++)
            {
                int mid = (lst + qr[i][j] + 1) / 2;

                vr.pb({mid, i});

                lst = qr[i][j];
            }
        }

        if (!f) {for (int i = 0; i < q; i++) cout << -1 << endl; exit(0);}

        vector <pair <int, int> > v; v.resize(q);

        for (int i = 0; i < q; i++) {cin >> v[i].F >> v[i].S; v[i].S = i;}

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

        sort(vr.begin(), vr.end());

        int ans[q], j = 0;

        for (auto it : v)
        {
            int nm = it.S, x = it.F;

            while (j < sz(vr) && vr[j].F <= x)
            {
                int tp = vr[j].S;

                se.erase({qr[tp][pos[tp]], tp});

                pos[tp]++;

                se.insert({qr[tp][pos[tp]], tp});

                j++;
            }

            ans[nm] = max(abs((*se.begin()).F - x), abs((*se.rbegin()).F - x));
        }

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

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