Submission #885352

#	Time	Username	Problem	Language	Result	Execution time	Memory
885352		Koyote	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	324 ms	103648 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
 
// Persistent Segment Tree
struct node {
    node *l, *r;
    int val;
    node() : l(0), r(0), val(0) {}
    node(int _v) : l(0), r(0), val(_v) {}
    node(node *_l, node *_r) : l(_l), r(_r), val(l->val + r->val) {}
    void extend() {
        if (!l) l = new node();
        if (!r) r = new node();
    }
};
 
node* update(node *cur, int p, int v, int l, int r) {
    if (l == r) return new node(cur->val + v);
    cur->extend();
    int mid = (l + r) >> 1;
    if (p <= mid) return new node(update(cur->l, p, v, l, mid), cur->r);
    else return new node(cur->l, update(cur->r, p, v, mid + 1, r));
}
 
int query(node *cur, int qs, int qe, int l, int r) {
    if (r < qs || qe < l) return 0;
    if (qs <= l && r <= qe) return cur->val;
    cur->extend();
    int mid = (l + r) >> 1;
    return query(cur->l, qs, qe, l, mid) + query(cur->r, qs, qe, mid + 1, r);
}
// End of Persistent Segment Tree

// Merge Sort Tree
template<class T> struct merge_sort_tree {
    int _l, _r, _m;
    vector<T> v;
    merge_sort_tree *left, *right;
    merge_sort_tree(int l, int r, vector<T> &e) {
        v.resize(r - l + 1);
        _l = l, _r = r, _m = (l + r) >> 1, v[0] = e[l];
        if (l == r) left = right = nullptr;
        else {
            left = new merge_sort_tree(_l, _m, e);
            right = new merge_sort_tree(_m + 1, _r, e);
            vector<T> v1 = left->v, v2 = right->v;
            v.clear();
            int s1 = sz(v1), s2 = sz(v2);
            v.reserve(s1 + s2);
            int i = 0, j = 0;
            while (i < s1 && j < s2) v.push_back(v1[i] <= v2[j] ? v1[i++] : v2[j++]);
            while (i < s1) v.push_back(v1[i++]);
            while (j < s2) v.push_back(v2[j++]);
        }
    }
    int count(int l, int r, T a, T b) {
        if (a > b) return 0;
        if (l > _r || r < _l) return 0;
        if (_l >= l && _r <= r) return upper_bound(all(v), b) - lower_bound(all(v), a);
        return left->count(l, r, a, b) + right->count(l, r, a, b);
    }
};
// End of Merge Sort Tree
 
const int N = 2e5 + 7, N2 = 6e5 + 2, LG = 22;
int n, k, a[N], b[N], t[N], t_idx[N2], max_t_idx[LG][N2];
 
constexpr int lg2(const int x) { return 31 - __builtin_clz(x); }
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    for (int i = 1; i <= k; i++) cin >> t[i];
 
    basic_string<int> cmpr; cmpr.reserve(2 * n + k + 1), cmpr += 0;
    for (int i = 1; i <= n; i++) cmpr += a[i], cmpr += b[i];
    for (int i = 1; i <= k; i++) cmpr += t[i];
    sort(all(cmpr)), cmpr.erase(unique(all(cmpr)), cmpr.end());

    auto search = [&](const int v) -> int { return lower_bound(all(cmpr), v) - cmpr.begin(); };
    for (int i = 1; i <= n; i++) a[i] = search(a[i]), b[i] = search(b[i]);
    for (int i = 1; i <= k; i++) t[i] = search(t[i]);
 
    // for (int i = 0; i <= sz(cmpr); i++) t_idx[i] = -1;
    for (int i = 1; i <= k; i++) t_idx[t[i]] = i;

    // Sparse table
    for (int i = 1; i <= sz(cmpr); i++)
        max_t_idx[0][i] = t_idx[i];
    for (int j = 1; j < LG; j++)
        for (int i = 1; i + (1 << j) - 1 <= sz(cmpr); i++)
            max_t_idx[j][i] = max(max_t_idx[j - 1][i], max_t_idx[j - 1][i + (1 << (j - 1))]);
    
    auto query_max_t_idx = [&](int l, int r) -> int {
        int len = lg2(r - l + 1);
        return max(max_t_idx[len][l], max_t_idx[len][r - (1 << len) + 1]);
    };
    // End of Sparse table

    // Persistent Segment Tree
    // vector<node*> roots;
    // roots.reserve(k + 1), roots.push_back(new node());
    // for (int i = 1; i <= k; i++) 
    //     roots.push_back(update(roots.back(), t[i], 1, 1, sz(cmpr)));
    // auto cnt_on_range = [&](int l, int r, int x, int y) -> int {
    //     // Number of elements a[l..r] that x <= a[i] <= y;
    //     return query(roots[r], x, y, 1, sz(cmpr)) - query(roots[l - 1], x, y, 1, sz(cmpr));
    // };
    // End of Persistent Segment Tree

    // Merge Sort Tree
    vector<int> vector_t(t, t + k + 1);
    merge_sort_tree<int> mst(0, k + 1, vector_t);
    auto cnt_on_range = [&](int l, int r, int x, int y) -> int {
        return mst.count(l, r, x, y);
    };
    // End of Merge Sort Tree
 
    basic_string<int> ans; ans.reserve(n);
    for (int i = 1; i <= n; i++) {
        if (a[i] == b[i]) { ans += cmpr[a[i]]; continue; }
        bool swapped = (a[i] > b[i] ? (swap(a[i], b[i]), true) : false);
        int last_pos = query_max_t_idx(a[i], b[i] - 1);
        int cnt_flipped = cnt_on_range(last_pos + 1, k, b[i], sz(cmpr));
 
        if (last_pos != 0 || swapped) swap(a[i], b[i]);
        ans += cmpr[~cnt_flipped & 1 ? a[i] : b[i]];
    }
    cout << accumulate(ans.begin(), ans.end(), 0LL) << '\n';
}

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