Submission #391907

#	Time	Username	Problem	Language	Result	Execution time	Memory
391907		blue	New Home (APIO18_new_home)	C++17	0 / 100	5085 ms	33552 KiB

new_home

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const int mx = 300000;

int n, k, q;
int x[mx], t[mx], a[mx], b[mx];
int l[mx], y[mx];

int T(int i)
{
    // cerr << "T(" << i << ")\n";
    if(i < n)
    {
        // cerr << "case 1\n";
        return a[i];
    }
    else if(i < n+q)
    {
        // cerr << "case 2\n";
        // cerr << "i-n " << i-n << ' ' << y[i-n] << '\n';
        return y[i-n];
    }
    else
    {
        // cerr << "case 3\n";
        return b[i-n-q];
    }
}

int main()
{
    cin >> n >> k >> q;

    for(int i = 0; i < n; i++)
    {
        cin >> x[i] >> t[i] >> a[i] >> b[i];
        t[i]--;
    }

    for(int j = 0; j < q; j++) cin >> l[j] >> y[j];

    int I[n+q+n];
    for(int i = 0; i < n+q+n; i++)
        I[i] = i;

    sort(I, I+n+q+n, [] (int r, int s)
    {
        int t1 = T(r);
        int t2 = T(s);
        if(t1 == t2) return r < s;
        else return t1 < t2;
    });

    for(int i:I) cerr << i << ' ' << T(i) << '\n';
    cerr << '\n';

    vector<long long> res(q, 0);

    multiset<int> stores[k];

    for(int i:I)
    {
        cerr << i << '\n';
        if(i < n)
        {
            stores[t[i]].insert(x[i]);
        }
        else if(i < n+q)
        {
            cerr << "query " << i-n << '\n';
            for(int typ = 0; typ < k; typ++)
            {
                int temp = 1e9;
                for(int s: stores[t[typ]])
                {
                    cerr << s << ' ';
                    temp = min(temp, abs(s - l[i-n]));
                }
                cerr << '\n';

                res[i-n] = max(res[i-n], (long long)temp);
            }
            if(res[i-n] == 1e9)
            {
                res[i-n] = -1;
            }
            cerr << '\n';
        }
        else
        {
            stores[t[i-n-q]].erase(stores[t[i-n-q]].find(x[i-n-q]));
        }
    }
    cerr << '\n';

    for(int j = 0; j < q; j++) cout << res[j] << '\n';
}

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