Submission #160596

#	Time	Username	Problem	Language	Result	Execution time	Memory
160596		Minnakhmetov	New Home (APIO18_new_home)	C++14	10 / 100	1094 ms	67660 KiB

new_home

#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
  
using namespace std;

const int N = 3e5 + 5, INF = 1e9;
vector<int> v[N];
int ans[N];

struct E {
    int p, t, w, x;
};

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

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

    for (int i = 0; i < n; i++) {
        int x, t, a, b;
        cin >> x >> t >> a >> b;
        t--;
        v[t].push_back(x);
    }

    bool ok = true;

    vector<E> evs;

    for (int i = 0; i < k; i++) {
        if (v[i].empty()) {
            ok = false;
        }

        sort(all(v[i]));

        evs.push_back({1, 0, 1, v[i][0]});
        evs.push_back({v[i][0], 1, 1, v[i][0]});

        evs.push_back({v[i].back(), 0, 0, v[i].back()});

        v[i].erase(unique(all(v[i])), v[i].end());

        for (int j = 0; j + 1 < v[i].size(); j++) {
            int m = (v[i][j + 1] + v[i][j]) / 2;
            evs.push_back({v[i][j], 0, 0, v[i][j]});
            evs.push_back({m + 1, 1, 0, v[i][j]});

            evs.push_back({m + 1, 0, 1, v[i][j + 1]});
            evs.push_back({v[i][j + 1], 1, 1, v[i][j + 1]});
        }
    }

    sort(all(evs), [](const E &a, const E &b) {
        return a.p == b.p ? a.t < b.t : a.p < b.p;
    });

    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        evs.push_back({x, 2, i});
    }

    sort(all(evs), [](const E &a, const E &b) {
        return a.p == b.p ? a.t < b.t : a.p < b.p;
    });

    multiset<int> st[2];

    for (E e : evs) {

        if (e.t == 0) {
            st[e.w].insert(e.x);
        }
        else if (e.t == 1) {
            st[e.w].erase(st[e.w].find(e.x));
        }
        else if (e.t == 2) {
            if (ok) {
                ans[e.w] = -1;
                if (!st[0].empty()) {
                    ans[e.w] = max(ans[e.w], e.p - *st[0].begin());
                }
                if (!st[1].empty()) {
                    ans[e.w] = max(ans[e.w], *st[1].rbegin() - e.p);
                }
            }
            else {
                ans[e.w] = -1;
            }
        }
    }

    for (int i = 0; i < q; i++) {
        cout << ans[i] << "\n";
    }



    return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:48:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j + 1 < v[i].size(); j++) {
                         ~~~~~~^~~~~~~~~~~~~

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