oj.uz

Submission #218818

# Submission time Handle Problem Language Result Execution time Memory
218818 2020-04-02T19:20:38 Z VEGAnn New Home (APIO18_new_home) C++14
0 / 100
 415 ms 48724 KB 
#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();

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

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

    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 9 ms 7424 KB Output is correct
2 Incorrect 9 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 9 ms 7424 KB Output is correct
2 Incorrect 9 ms 7424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 415 ms 48724 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 390 ms 46036 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.0

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