Submission #218827

#	Time	Username	Problem	Language	Result	Execution time	Memory
218827		VEGAnn	New Home (APIO18_new_home)	C++14	0 / 100	332 ms	22120 KiB

new_home

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define MP make_pair
#define PB push_back
#define pii pair<int,int>
#define pi3 pair<pii,int>
#define ft first
#define sd second
#define sz(x) ((int)x.size())
using namespace std;
const int N = 300100;
const int oo = int(2e9) + 7;
vector<int> vc[N];
vector<pii> qr;
int n, k, q, ans[N], l[N];

bool bigger(pii a, pii b){
    b.sd -= (a.ft - b.ft);
    return b.sd > a.sd;
}

void check(){
    qr.clear();

    for (int i = 0; i < k; i++){
        qr.PB(MP(0, -vc[i][0]));

        for (int it = 1; it < sz(vc[i]); it++){
            int len = (vc[i][it] - vc[i][it - 1]);
            qr.PB(MP(len / 2 + vc[i][it - 1], -len / 2));
        }
    }

    for (int i = 0; i < q; i++)
        qr.PB(MP(l[i], i));

    sort(all(qr));

    pii mx = MP(0, 0);

    for (pii cr : qr)
        if (cr.sd < 0){
            cr.sd = -cr.sd;
            if (bigger(mx, cr))
                mx = cr;
        } else {
            ans[cr.sd] = max(ans[cr.sd], mx.sd - (cr.ft - mx.ft));
        }
}

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 j, t, x;
        cin >> x >> t >> j >> j;
        x += x;
        t--;
        vc[t].PB(x);
    }

    for (int i = 0; i < k; i++) {
        if (sz(vc[i]) == 0){
            for (; q; q--) cout << "-1\n";
            return 0;
        }

        sort(all(vc[i]));
    }

    for (int i = 0; i < q; i++) {
        int j;
        cin >> l[i] >> j;
        l[i] += l[i];
        ans[i] = 0;
    }

    check();

  	return 0;
  
    for (int i = 0; i < q; i++)
        l[i] = int(2e8) - l[i];

    for (int i = 0; i < k; i++)
        for (int &cr : vc[i]) {
            cr = int(2e8) - cr;
        }

    check();

    for (int i = 0; i < q; i++)
        cout << (ans[i] == oo ? -1 : ans[i] / 2) << '\n';

    return 0;
}

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