제출 #1278762

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278762		tuongll	운세 보기 2 (JOI14_fortune_telling2)	C++20	100 / 100	172 ms	20208 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;

struct Sparse_Table {
    vector<vector<int>> st;
    Sparse_Table(const vector<int> &a){
        int n = (int)a.size() - 1;
        st.resize(__lg(n) + 1);
        for (int j = 0; (1 << j) <= n; ++j)
            st[j].resize(n + 1);

        for (int i = 1; i <= n; ++i)
            st[0][i] = a[i];
        for (int j = 1; (1 << j) <= n; ++j){
            for (int i = 1; i + (1 << j) - 1 <= n; ++i)
                st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
        }
    }

    int query(int l, int r){
        int k = __lg(r - l + 1);
        return max(st[k][l], st[k][r - (1 << k) + 1]);
    }
};

struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick(int n): n(n), bit(n + 1) {}

    void update(int i, int x){
        for (; i <= n; i += i & -i)
            bit[i] += x;
    }

    int get(int i){
        int res = 0;
        for (; i; i -= i & -i)
            res += bit[i];
        return res;
    }
    int get(int l, int r){
        return get(r) - get(l - 1);
    }
};

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

    int n, k; cin >> n >> k;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i] >> b[i];

    vector<int> t(k + 1), co;
    for (int j = 1; j <= k; ++j){
        cin >> t[j];
        co.push_back(t[j]);
    }

    co.push_back(0); // so stuff is 1-indexed or whatever
    sort(begin(co), end(co));
    co.erase(unique(begin(co), end(co)), end(co));
    int m = (int)co.size() - 1;

    vector<int> pos(n), cnt(n);
    {
        vector<int> T(m + 1, 0);
        for (int i = 1; i <= k; ++i){
            int idx = lower_bound(begin(co), end(co), t[i]) - begin(co);
            T[idx] = i;
        }

        Sparse_Table st(T);
        for (int i = 0; i < n; ++i){
            int u = a[i], v = b[i];
            if (u > v) swap(u, v);

            int l = lower_bound(begin(co), end(co), u) - begin(co);
            int r = lower_bound(begin(co), end(co), v) - begin(co) - 1;
            if (l <= r) pos[i] = st.query(l, r);
        }
    }

    {
        vector<vector<int>> qr(k + 1);
        for (int i = 0; i < n; ++i) if (pos[i] < k)
            qr[pos[i] + 1].push_back(i);

        Fenwick bit(m);
        for (int j = k; j >= 1; --j){
            int idx = lower_bound(begin(co), end(co), t[j]) - begin(co);
            bit.update(idx, 1);

            for (int i : qr[j]){
                idx = lower_bound(begin(co), end(co), max(a[i], b[i])) - begin(co);
                cnt[i] = bit.get(idx, m);
            }
        }
    }

    long long res = 0;
    for (int i = 0; i < n; ++i){
        // this mf exists => top side is always max
        if (pos[i] > 0){
            if (a[i] < b[i]) swap(a[i], b[i]);
        }
        // all t[j] >= max(a[i], b[i]) later => always a flip
        if (cnt[i] & 1) swap(a[i], b[i]);

        res += a[i];
    }

    cout << res << '\n';
}

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