Submission #217734

#	Time	Username	Problem	Language	Result	Execution time	Memory
217734		Vimmer	New Home (APIO18_new_home)	C++14	12 / 100	2831 ms	20072 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];

pair <int, int> dist[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;

            cin >> x >> t;

            vr.pb({x, t});

            qr[t].pb(x);
        }

        set <pair <int, int> > sel, ser; sel.clear(); ser.clear();

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

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

        bool f = 1;

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

            dist[i] = {-1, qr[i][0]};

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

        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());

        int lst = 0, 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, xr = vr[j].F;

                if (dist[tp].F != -1) sel.erase({qr[tp][pos[tp] - 1], tp});

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

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

                dist[tp].F = qr[tp][pos[tp]];

                pos[tp]++;

                if (pos[tp] != sz(qr[tp])) ser.insert({qr[tp][pos[tp]], tp});

                j++;
            }

            int mx = 0;

            if (sz(sel) != 0) mx = max(mx, x - (*sel.begin()).F);

            if (sz(ser) != 0) mx = max(mx, (*ser.rbegin()).F - x);

            ans[nm] = mx;
        }

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

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:148:35: warning: unused variable 'xr' [-Wunused-variable]
                 int tp = vr[j].S, xr = vr[j].F;
                                   ^~
new_home.cpp:140:13: warning: unused variable 'lst' [-Wunused-variable]
         int lst = 0, ans[q], j = 0;
             ^~~

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