Submission #217701

#	Time	Username	Problem	Language	Result	Execution time	Memory
217701		VEGAnn	New Home (APIO18_new_home)	C++14	12 / 100	2044 ms	27336 KiB

new_home

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define PB push_back
#define pii pair<int,int>
#define ft first
#define sd second
#define MP make_pair
#define MP3(a,b,c) MP(MP(a,b),c)
#define pi3 pair<pii,int>
using namespace std;
typedef long long ll;
const int N = 300100;
const int M = 200100;
const int K = 410;
const int oo = 2e9;
vector<pi3> qr;
multiset<int> st[K];
multiset<int>::iterator ite;
int ans[N], n, k, q;

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

//    freopen("in.txt","r",stdin);

    cin >> n >> k >> q;

    for (int i = 0; i < n; i++){
        int x, t, a, b;
        cin >> x >> t >> a >> b;

        qr.PB(MP3(a, -t, x));
        qr.PB(MP3(b + 1, -t, -x));
    }

    for (int i = 0; i < q; i++){
        int y, l; cin >> l >> y;
        qr.PB(MP3(y, l, i));
    }

    sort(all(qr));

    for (pi3 cr : qr)
        if (cr.ft.sd < 0){
            int tp = -cr.ft.sd;

            if (cr.sd < 0)
                st[tp].erase(st[tp].find(-cr.sd));
            else st[tp].insert(cr.sd);
        } else {

            int res = 0;

            for (int tp = 1; tp <= k; tp++){
                if (!sz(st[tp])){
                    res = oo;
                    break;
                }

                int cur = oo;

                ite = st[tp].upper_bound(cr.ft.sd);

                if (ite != st[tp].end())
                    cur = min(cur, (*ite) - cr.ft.sd);

                if (ite != st[tp].begin())
                    cur = min(cur, cr.ft.sd - (*prev(ite)));

                res = max(res, cur);
            }

            ans[cr.sd] = (res == oo ? -1 : res);
        }

    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';

    return 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