oj.uz

Submission #160592

# Submission time Handle Problem Language Result Execution time Memory
160592 2019-10-28T16:20:15 Z Minnakhmetov New Home (APIO18_new_home) C++14
0 / 100
 1071 ms 49028 KB 
#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()});

        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, 0, v[i][j]});

            evs.push_back({m, 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:46: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 8 ms 7416 KB Output is correct
2 Incorrect 8 ms 7420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1071 ms 47504 KB Output is correct
2 Incorrect 630 ms 49028 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 812 ms 46328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.0

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