Submission #1203112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203112		saidpon	New Home (APIO18_new_home)	C++20	0 / 100	5093 ms	46424 KiB

new_home

#include <bits/stdc++.h>
#define nemeshay ios_base::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
#define int long long
#define sigma signed
#define pb push_back
#define ar array
using namespace std;
const int N = 1e6 + 2, inf = 1e9 + 7, mod = 998244353;
int ans[N];
void test_case(){
    int n, k, q;
    cin >> n >> k >> q;
    vector <ar<int, 3>> queries, pon[2];
    multiset <int> ok[k + 1];
    for (int i = 1; i <= k; i++) ok[i].insert(-inf), ok[i].insert(inf);
    for (int i = 0; i < n; i++){
        int x, t, a, b;
        cin >> x >> t >> a >> b;
        pon[0].pb({a, t, x});
        pon[1].pb({b, t, x});
    }
    for (int i = 0; i < 2; i++) sort (pon[i].rbegin(), pon[i].rend());
    for (int i = 0; i < q; i++){
        int l, y;
        cin >> l >> y;
        queries.pb({y, l, i});
    }
    sort (queries.begin(), queries.end());
    for (auto j: queries){
        while (pon[0].size()){
            auto [a, t, x] = pon[0].back();
            if (a > j[0]) break;
            ok[t].insert(x);
            pon[0].pop_back();
        }
        while (pon[1].size()){
            auto [a, t, x] = pon[1].back();
            if (a > j[0]) break;
            ok[t].erase(ok[t].find(x));
            pon[1].pop_back();
        }
        int mx = 0;
        for (int i = 1; i <= k; i++) {
            if (ok[i].size() == 2) {
                mx = -1;
                break;
            }
            auto x = *ok[i].upper_bound(j[1]);
            auto y = ok[i].upper_bound(j[1]);
            y--;
            mx = max(mx, min(abs(j[1] - x), abs(j[1] - *y)));
        }
        ans[j[2]] = mx;
    }
    for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}
sigma main() {
    int t = 1;
    while (t--) test_case();
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
*/

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