제출 #390079

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
390079		KoD	운세 보기 2 (JOI14_fortune_telling2)	C++17	100 / 100	488 ms	34408 KiB

fortune_telling2

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

template <class T>
void fix(Vec<T>& vec) {
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
}

template <class T>
int lowb(const Vec<T>& vec, const T& x) {
    return std::lower_bound(vec.cbegin(), vec.cend(), x) - vec.cbegin();
}

template <class T>
int upb(const Vec<T>& vec, const T& x) {
    return std::upper_bound(vec.cbegin(), vec.cend(), x) - vec.cbegin();
}

template <class T>
void setmax(T& lhs, const T& rhs) {
    if (lhs < rhs) {
        lhs = rhs;
    }
}

struct Segtree {
    int size;
    Vec<int> data;
    Segtree(const int n): size(n), data(2 * n, -1) {}
    
    void chmax(int l, int r, const int x) {
        l += size;
        r += size;
        while (l < r) {
            if (l & 1) setmax(data[l++], x);
            if (r & 1) setmax(data[--r], x);
            l >>= 1;
            r >>= 1;
        }
    }

    int get(int i) const {
        int ret = -1;
        i += size;
        while (i > 0) {
            setmax(ret, data[i]);
            i >>= 1;
        }
        return ret;
    }
};

struct Fenwick {
    Vec<int> data;
    Fenwick(const int n): data(n + 1) { }

    void add(int i) {
        for (i += 1; i < (int) data.size(); i += i & -i) {
            data[i] ^= 1;
        }
    }

    int get(int i) const {
        int ret = 0;
        for (; i > 0; i -= i & -i) {
            ret ^= data[i];
        }
        return ret;
    }

    int fold(const int l, const int r) const {
        return get(l) ^ get(r);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, Q;
    std::cin >> N >> Q;
    Vec<int> A(N), B(N), T(Q);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i] >> B[i];
    }
    for (int i = 0; i < Q; ++i) {
        std::cin >> T[i];
    }

    Vec<int> xs, ys, ts;
    xs.reserve(N);
    ys.reserve(N);
    for (int i = 0; i < N; ++i) {
        xs.push_back(std::min(A[i], B[i]));
        ys.push_back(std::max(A[i], B[i]));
    }
    fix(xs);
    fix(ys);
    ts = T;
    fix(ts);

    Vec<int> xid(N), yid(N), tid(Q);
    for (int i = 0; i < N; ++i) {
        xid[i] = lowb(xs, std::min(A[i], B[i]));
        yid[i] = lowb(ys, std::max(A[i], B[i]));
    }
    for (int i = 0; i < Q; ++i) {
        tid[i] = lowb(ts, T[i]);
    }

    Vec<int> time(N);
    {
        Vec<Vec<int>> qs(xs.size());
        for (int i = 0; i < N; ++i) {
            qs[xid[i]].push_back(i);
        }
        Vec<Vec<int>> add(xs.size());
        for (int i = 0; i < Q; ++i) {
            const auto x = upb(xs, T[i]);
            if (x > 0) {
                add[x - 1].push_back(i);
            }
        }
        Segtree seg(ys.size());
        for (int x = (int) xs.size() - 1; x >= 0; --x) {
            for (const auto i: add[x]) {
                seg.chmax(upb(ys, T[i]), (int) ys.size(), i);
            }
            for (const auto i: qs[x]) {
                time[i] = seg.get(yid[i]);
            }
        }
    }

    Vec<int> cnt(N);
    {
        Vec<Vec<int>> qs(Q);
        for (int i = 0; i < N; ++i) {
            if (time[i] != Q - 1) {
                qs[time[i] + 1].push_back(i);
            }
        }
        Fenwick fen(ts.size());
        for (int q = Q - 1; q >= 0; --q) {
            fen.add(tid[q]);
            for (const auto i: qs[q]) {
                cnt[i] = fen.fold(lowb(ts, std::max(A[i], B[i])), (int) ts.size());
            }
        }
    }

    long long sum = 0;
    for (int i = 0; i < N; ++i) {
        sum += ((time[i] >= 0 or A[i] >= B[i]) ^ cnt[i]) ? std::max(A[i], B[i]) : std::min(A[i], B[i]);
    }
    std::cout << sum << '\n';

    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65