Submission #218833

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
218833	2020-04-02T19:39:00 Z	VEGAnn	New Home (APIO18_new_home)	C++14	10 / 100	468 ms	41320 KB

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 + 1));

    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 - 1] = max(ans[cr.sd - 1], 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();

    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;
        }
        reverse(all(vc[i]));
    }

    check();

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

    return 0;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	7424 KB	Output is correct
2	Incorrect	8 ms	7424 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	7424 KB	Output is correct
2	Incorrect	8 ms	7424 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	438 ms	21220 KB	Output is correct
2	Correct	382 ms	32040 KB	Output is correct
3	Correct	468 ms	41320 KB	Output is correct
4	Correct	446 ms	35176 KB	Output is correct
5	Correct	382 ms	31716 KB	Output is correct
6	Correct	375 ms	31816 KB	Output is correct
7	Correct	412 ms	41320 KB	Output is correct
8	Correct	422 ms	34916 KB	Output is correct
9	Correct	400 ms	33640 KB	Output is correct
10	Correct	398 ms	32868 KB	Output is correct
11	Correct	355 ms	31976 KB	Output is correct
12	Correct	389 ms	32752 KB	Output is correct