Submission #1173934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173934		Muhammet	New Home (APIO18_new_home)	C++20	0 / 100	902 ms	70572 KiB

new_home

#include "bits/stdc++.h"

using namespace std;
 
#define ll long long
#define SZ(s) (int)s.size()
#define ff first
#define ss second

const int N = 3e5 + 5;
const int M = 1e9 + 7;

vector <int> vc[N];

map <int, int> ans;

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

    int n, k, q;
    cin >> n >> k >> q;

    vector <int> x(n+1), t(n+1), a(n+1), b(n+1);
    set <pair <int, int>> v1;
    for(int i = 1; i <= n; i++) {
        cin >> x[i] >> t[i] >> a[i] >> b[i];
        v1.insert({x[i], t[i]});
        vc[t[i]].push_back(x[i]);
    }


    vector <int> l(q+1), y2(q+1);
    for(int i = 1; i <= q; i++) {
        cin >> l[i] >> y2[i];
        v1.insert({l[i], 0});
    }
    vector <pair <int, int>> v;
    for(auto i : v1) {
        v.push_back(i);
    }

    for(int i = 1; i <= k; i++) {
        if(!SZ(vc[i])) {
            for(int j = 1; j <= q; j++) {
                cout << -1 << "\n";
            }
            return 0;
        }
        sort(vc[i].begin(), vc[i].end());
    }
    
    sort(v.begin(), v.end());

    multiset <int> s_left, s_right;
    multiset <pair <int, pair <int, int>>> s_change;
    for(int i = 1; i <= k; i++) {
        s_right.insert(vc[i][0]);
    }
    for(auto [y, tp] : v) {
        while(SZ(s_change)) {
            auto c = (*s_change.begin());
            if(c.ff > y) break;
            s_change.erase(s_change.begin());
            auto [num, type] = c.ss;
            s_left.erase(s_left.find(num));
            s_right.insert(*upper_bound(vc[type].begin(), vc[type].end(), num));
        }
        if(!tp) {
            int xy = 0;
            if(SZ(s_left)) xy = max(xy, abs(*s_left.begin() - y));
            if(SZ(s_right)) xy = max(xy, abs(*s_right.rbegin() - y));
            ans[y] = xy;
            continue;
        }
        s_right.erase(s_right.find(y));
        s_left.insert(y);
        if(y == vc[tp].back()) continue;
        int y1 = (y + *upper_bound(vc[tp].begin(), vc[tp].end(), y)) / 2;
        s_change.insert({y1, {y, tp}});
    }

    for(int i = 1; i <= q; i++) {
        cout << ans[l[i]] << "\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