Submission #160596

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
160596	2019-10-28T16:34:24 Z	Minnakhmetov	New Home (APIO18_new_home)	C++14	10 / 100	1094 ms	67660 KB

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

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.0

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

Subtask #2
0 / 7.0

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

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	979 ms	43252 KB	Output is correct
2	Correct	628 ms	41732 KB	Output is correct
3	Correct	981 ms	67584 KB	Output is correct
4	Correct	1094 ms	55068 KB	Output is correct
5	Correct	594 ms	48828 KB	Output is correct
6	Correct	621 ms	48680 KB	Output is correct
7	Correct	932 ms	67660 KB	Output is correct
8	Correct	1042 ms	54880 KB	Output is correct
9	Correct	917 ms	51584 KB	Output is correct
10	Correct	904 ms	49884 KB	Output is correct
11	Correct	841 ms	48956 KB	Output is correct
12	Correct	725 ms	49740 KB	Output is correct