oj.uz

Submission #885352

# Submission time Handle Problem Language Result Execution time Memory
885352 2023-12-09T14:08:06 Z Koyote Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 324 ms 103648 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25176 KB Output is correct
2 Correct 4 ms 25432 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 4 ms 27228 KB Output is correct
5 Correct 4 ms 27224 KB Output is correct
6 Correct 4 ms 27228 KB Output is correct
7 Correct 4 ms 27228 KB Output is correct
8 Correct 4 ms 27228 KB Output is correct
9 Correct 4 ms 27228 KB Output is correct
10 Correct 3 ms 25432 KB Output is correct
11 Correct 4 ms 25176 KB Output is correct
12 Correct 5 ms 25180 KB Output is correct
13 Correct 5 ms 27224 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25176 KB Output is correct
2 Correct 4 ms 25432 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 4 ms 27228 KB Output is correct
5 Correct 4 ms 27224 KB Output is correct
6 Correct 4 ms 27228 KB Output is correct
7 Correct 4 ms 27228 KB Output is correct
8 Correct 4 ms 27228 KB Output is correct
9 Correct 4 ms 27228 KB Output is correct
10 Correct 3 ms 25432 KB Output is correct
11 Correct 4 ms 25176 KB Output is correct
12 Correct 5 ms 25180 KB Output is correct
13 Correct 5 ms 27224 KB Output is correct
14 Correct 15 ms 35932 KB Output is correct
15 Correct 27 ms 46600 KB Output is correct
16 Correct 39 ms 51424 KB Output is correct
17 Correct 54 ms 54064 KB Output is correct
18 Correct 53 ms 54076 KB Output is correct
19 Correct 50 ms 54072 KB Output is correct
20 Correct 56 ms 54072 KB Output is correct
21 Correct 50 ms 54048 KB Output is correct
22 Correct 42 ms 54100 KB Output is correct
23 Correct 40 ms 52140 KB Output is correct
24 Correct 40 ms 49972 KB Output is correct
25 Correct 46 ms 54028 KB Output is correct
26 Correct 52 ms 54072 KB Output is correct
27 Correct 75 ms 54048 KB Output is correct
28 Correct 54 ms 54072 KB Output is correct
29 Correct 113 ms 54176 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25176 KB Output is correct
2 Correct 4 ms 25432 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 4 ms 27228 KB Output is correct
5 Correct 4 ms 27224 KB Output is correct
6 Correct 4 ms 27228 KB Output is correct
7 Correct 4 ms 27228 KB Output is correct
8 Correct 4 ms 27228 KB Output is correct
9 Correct 4 ms 27228 KB Output is correct
10 Correct 3 ms 25432 KB Output is correct
11 Correct 4 ms 25176 KB Output is correct
12 Correct 5 ms 25180 KB Output is correct
13 Correct 5 ms 27224 KB Output is correct
14 Correct 15 ms 35932 KB Output is correct
15 Correct 27 ms 46600 KB Output is correct
16 Correct 39 ms 51424 KB Output is correct
17 Correct 54 ms 54064 KB Output is correct
18 Correct 53 ms 54076 KB Output is correct
19 Correct 50 ms 54072 KB Output is correct
20 Correct 56 ms 54072 KB Output is correct
21 Correct 50 ms 54048 KB Output is correct
22 Correct 42 ms 54100 KB Output is correct
23 Correct 40 ms 52140 KB Output is correct
24 Correct 40 ms 49972 KB Output is correct
25 Correct 46 ms 54028 KB Output is correct
26 Correct 52 ms 54072 KB Output is correct
27 Correct 75 ms 54048 KB Output is correct
28 Correct 54 ms 54072 KB Output is correct
29 Correct 113 ms 54176 KB Output is correct
30 Correct 129 ms 97104 KB Output is correct
31 Correct 161 ms 99608 KB Output is correct
32 Correct 199 ms 100164 KB Output is correct
33 Correct 299 ms 103648 KB Output is correct
34 Correct 120 ms 97028 KB Output is correct
35 Correct 282 ms 103452 KB Output is correct
36 Correct 287 ms 103640 KB Output is correct
37 Correct 280 ms 103488 KB Output is correct
38 Correct 290 ms 103408 KB Output is correct
39 Correct 303 ms 103504 KB Output is correct
40 Correct 260 ms 103488 KB Output is correct
41 Correct 284 ms 103348 KB Output is correct
42 Correct 285 ms 103460 KB Output is correct
43 Correct 210 ms 103412 KB Output is correct
44 Correct 207 ms 103484 KB Output is correct
45 Correct 207 ms 103360 KB Output is correct
46 Correct 203 ms 101460 KB Output is correct
47 Correct 236 ms 99388 KB Output is correct
48 Correct 324 ms 101316 KB Output is correct
49 Correct 283 ms 101644 KB Output is correct