Submission #1294207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294207		goppamach	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	286 ms	18536 KiB

fortune_telling2

// #pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

#define el "\n"
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define mp make_pair
#define sqr(x) ((x) * (x))
#define FOR(i, l, r) for (int i = l; i <= (r); i++)
#define FOD(i, l, r) for (int i = l; i >= (r); i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) ((int)(x).size())
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr);

using db = long double;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vbool = vector<bool>;
using vvbool = vector<vbool>;

template<class T> inline bool chmax(T &a, T const &b) { return (a < b ? (a = b, true) : false); }
template<class T> inline bool chmin(T &a, T const &b) { return (a > b ? (a = b, true) : false); }

// #define DEBUG
#ifdef DEBUG
#include "D:\cpp\debug.h"
#else
#define debug(...)
#define debug_arr(...)
#endif

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

constexpr int N = 2E5 + 5;
constexpr int INF = 1E9 + 7;
constexpr ll INFLL = 4E18;
constexpr int MOD = 1E9 + 7; // 998244353
constexpr double EPS = 1E-10;

template<class T> struct SegmentTree {
    int n;
    vector<T> tree;

    SegmentTree(int n): n(n), tree(4 * n + 5) {}

    void update(int i, int l, int r, int k, T val) {
        if (l > r || l > k || k > r) return;
        if (l == r) {
            tree[i] = val;
            return;
        }
        int m = (l + r) / 2;
        update(i * 2, l, m, k, val);
        update(i * 2 + 1, m + 1, r, k, val);
        tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
    }

    T query(int i, int l, int r, int ql, int qr) {
        if (l > r || l > qr || r < ql || ql > qr) return 0;
        if (l >= ql && r <= qr) return tree[i];
        int m = (l + r) / 2;
        return max(query(i * 2, l, m, ql, qr), query(i * 2 + 1, m + 1, r, ql, qr));
    }

    void update(int k, T val) { return update(1, 1, n, k, val); }

    T query(int ql, int qr) { return query(1, 1, n, ql, qr); }
};

template<class T> struct BIT {
    int n;
    vector<T> bit;

    BIT(int n): n(n), bit(n + 5) {}

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

    T query(int i) const {
        T res = 0;
        for (; i >= 1; i -= i & -i) {
            res += bit[i];
        }
        return res;
    }

    T query(int l, int r) const {
        return query(r) - query(l - 1);
    }
};

struct Card {
    int a, b, t, state;
    Card() = default;
    Card(int a, int b, int t): a(a), b(b), t(t), state(0) {}
} card[N];
int threshold[N];
int n, k;

void solve() {
    cin >> n >> k;

    vi vals;
    FOR(i, 1, n) {
        int a, b;
        cin >> a >> b;
        card[i] = {a, b, 0};
        vals.push_back(a);
        vals.push_back(b);
    }

    FOR(i, 1, k) {
        cin >> threshold[i];
        vals.push_back(threshold[i]);
    }

    sort(all(vals));
    vals.erase(unique(all(vals)), vals.end());
    auto compress = [&vals](int x) {
        return int(lower_bound(all(vals), x) - vals.begin()) + 1;
    };

    FOR(i, 1, n) {
        card[i].a = compress(card[i].a);
        card[i].b = compress(card[i].b);
        if (card[i].a > card[i].b) {
            swap(card[i].a, card[i].b);
            card[i].state = 1;
        }
    }

    const int MAX = 2 * n + k + 5;
    SegmentTree<int> st(MAX);
    FOR(i, 1, k) {
        threshold[i] = compress(threshold[i]);
        st.update(threshold[i], i);
    }

    FOR(i, 1, n) {
        card[i].t = st.query(card[i].a, card[i].b - 1);
    }

    sort(card + 1, card + n + 1, [](Card const &a, Card const &b) {
        return a.t > b.t;
    });

    BIT<int> ft(MAX);
    int j = k;
    FOR(i, 1, n) {
        if (card[i].t > 0) card[i].state = 1;
        while (j > card[i].t) {
            ft.update(threshold[j], +1);
            j--;
        }
        int cnt = ft.query(card[i].b, MAX);
        card[i].state ^= cnt & 1;
    }

    ll res = 0;
    FOR(i, 1, n) {
        int idx = card[i].state == 0 ? card[i].a : card[i].b;
        res += vals[idx - 1];
    }

    cout << res << el;
}

int main() {
    fast_io
    #define LOCAL
    #ifndef LOCAL
    #define PROBLEM ""
    freopen(PROBLEM ".INP", "r", stdin);
    freopen(PROBLEM ".OUT", "w", stdout);
    #endif

    int t = 1;
    // cin >> t;
    while (t--) solve();
}

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