Submission #1173914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173914		Muhammet	새 집 (APIO18_new_home)	C++20	0 / 100	5092 ms	42016 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);
    vector <pair <int, int>> v;
    for(int i = 1; i <= n; i++) {
        cin >> x[i] >> t[i] >> a[i] >> b[i];
        v.push_back({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];
        v.push_back({l[i], 0});
    }

    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()) {
            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