oj.uz

답안 #568137

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
568137 2022-05-24T17:03:53 Z Cyanmond 새 집 (APIO18_new_home) C++17
0 / 100
 5000 ms 205636 KB 
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
 
#include <bits/stdc++.h>
 
using namespace std;
using i64 = int64_t;
 
constexpr int inf = 1000000100;
 
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)
#define RVP(i, n) for (int i = (n - 1); i >= 0; --i)
 
#define ALL(x) (x).begin(), (x).end()
 
struct PriqueErase {
    priority_queue<int, vector<int>, greater<int>> a, b;
 
    void push(int x) { a.push(x); }
 
    void erase(int x) { b.push(x); }
 
    int top() {
        while (not a.empty()) {
            const int v = a.top();
            if (b.empty()) {
                return v;
            } else if (v == b.top()) {
                a.pop();
                b.pop();
            } else {
                return v;
            }
        }
        return inf;
    }
};
 
int cnt_sp[2000000];
 
struct RIEPM {
    int n, siz;
    vector<PriqueErase> data;
 
    RIEPM(int n_) : n(n_) {
        siz = 1;
        while (siz < n) siz <<= 1;
        data.assign(2 * siz, PriqueErase());
    }
 
    void replace(int l, int r1, int r2, int v) {
        assert(0 <= l and l <= r1 and l <= r2 and r1 <= n and r2 <= n);
        vector<int> vs;
        for (int li = l + siz, ri = r1 + siz; li < ri; li >>= 1, ri >>= 1) {
            if (li & 1) {
                ++cnt_sp[li++];
                vs.push_back(li - 1);
            }
            if (ri & 1) {
                ++cnt_sp[--ri];
                vs.push_back(ri);
            }
        }
        for (int li = l + siz, ri = r2 + siz; li < ri; li >>= 1, ri >>= 1) {
            if (li & 1) {
                --cnt_sp[li++];
                vs.push_back(li - 1);
            }
            if (ri & 1) {
                --cnt_sp[--ri];
                vs.push_back(ri);
            }
        }
        for (const int i : vs) {
            if (cnt_sp[i] == 1) data[i].push(v);
            if (cnt_sp[i] == -1) data[i].erase(v);
            cnt_sp[i] = 0;
        }
    }
 
    void push(int l, int r, int v) {
        assert(0 <= l and l <= r and r <= n);
        for (l += siz, r += siz; l < r; l >>= 1, r >>= 1) {
            if (l & 1) data[l++].push(v);
            if (r & 1) data[--r].push(v);
        }
    }
 
    void erase(int l, int r, int v) {
        assert(0 <= l and l <= r and r <= n);
        for (l += siz, r += siz; l < r; l >>= 1, r >>= 1) {
            if (l & 1) data[l++].erase(v);
            if (r & 1) data[--r].erase(v);
        }
    }
 
    int top(int i) {
        assert(0 <= i and i < n);
        i += siz;
        int res = inf;
        while (i != 0) {
            res = min(res, data[i].top());
            i >>= 1;
        }
        return res;
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    fill(cnt_sp, cnt_sp + 2000000, 0);
 
    int N, K, Q;
    cin >> N >> K >> Q;
    vector<int> X(N), T(N), A(N), B(N);
    REP(i, N) {
        cin >> X[i] >> T[i] >> A[i] >> B[i];
        --T[i];
    }
    vector<int> L(Q), Y(Q);
    REP(i, Q) cin >> L[i] >> Y[i];
 
    auto reverse_points = [&]() {
        REP(i, N) X[i] = inf - X[i];
        REP(i, Q) L[i] = inf - L[i];
    };
 
    auto solve = [&]() {
        vector<int> press;
        REP(i, N) press.push_back(X[i]);
        // REP(i, Q) press.push_back(L[i]);
        sort(ALL(press));
        press.erase(unique(ALL(press)), press.end());
 
        auto get_key = [&](int i) { return (int)(lower_bound(ALL(press), i) - press.begin()); };
 
        const int M = (int)press.size();
        RIEPM hp(M);
 
        vector<tuple<int, int, int, int>> event;
        REP(i, N) {
            event.push_back({A[i], 0, X[i], T[i]});
            event.push_back({B[i] + 1, 1, X[i], T[i]});
        }
        REP(i, Q) event.push_back({Y[i], 2, L[i], i});
        sort(ALL(event));
 
        vector<map<int, int>> pd(K);
        vector<int> res(Q, -1);
 
        int cnt_zero = K;
        for (const auto &[c, qt, p, i] : event) {
            if (qt == 0) {
                if (pd[i].empty()) --cnt_zero;
                auto [itr, vld] = pd[i].insert({p, 1});
                if (not vld) {
                    ++itr->second;
                    continue;
                }
                auto itr_r = itr;
                ++itr_r;
                if (itr_r == pd[i].end()) {
                    hp.push(get_key(p), M, p);
                } else {
                    hp.push(get_key(p), get_key((p + itr_r->first + 2) / 2), p);
                }
                if (itr == pd[i].begin()) continue;
                auto itr_l = itr;
                --itr_l;
                const int l_id = get_key(itr_l->first);
                if (itr_r != pd[i].end()) {
                    hp.replace(l_id, get_key((itr_l->first + p + 2) / 2),
                               get_key((itr_l->first + itr_r->first + 2) / 2), itr_l->first);
                } else {
                    hp.replace(l_id, get_key((itr_l->first + p + 2) / 2), M, itr_l->first);
                }
            }
            if (qt == 1) {
                auto itr = pd[i].find(p);
                if (--(itr->second) != 0) {
                    continue;
                }
                pd[i].erase(p);
                if (pd[i].empty()) ++cnt_zero;
                auto itr_r = pd[i].upper_bound(p);
                if (itr_r != pd[i].end()) {
                    hp.erase(get_key(p), get_key((p + itr_r->first + 2) / 2), p);
                } else {
                    hp.erase(get_key(p), M, p);
                }
                if (itr_r == pd[i].begin()) continue;
                auto itr_l = itr_r;
                --itr_l;
                const int l_id = get_key(itr_l->first);
                if (itr_r != pd[i].end()) {
                    hp.replace(l_id, get_key((itr_l->first + itr_r->first + 2) / 2),
                               get_key((itr_l->first + p + 2) / 2), itr_l->first);
                } else {
                    hp.replace(l_id, M, get_key((itr_l->first + p + 2) / 2), itr_l->first);
                }
            }
            if (qt == 2) {
                if (cnt_zero != 0) continue;
                const int pi = get_key(p);
                const int vi = hp.top(pi);
                if (vi == inf) continue;
                res[i] = p - vi;
            }
        }
 
        return res;
    };
 
    const auto res1 = solve();
    reverse_points();
    const auto res2 = solve();
    REP(i, Q) {
        const int ans = max(res1[i], res2[i]);
        cout << ans << '\n';
    }
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8020 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 3 ms 8148 KB Output is correct
4 Incorrect 9 ms 8148 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8020 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 3 ms 8148 KB Output is correct
4 Incorrect 9 ms 8148 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3640 ms 205636 KB Output is correct
2 Incorrect 3165 ms 178996 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5042 ms 203440 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8020 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 3 ms 8148 KB Output is correct
4 Incorrect 9 ms 8148 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8020 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 3 ms 8148 KB Output is correct
4 Incorrect 9 ms 8148 KB Output isn't correct
5 Halted 0 ms 0 KB -