oj.uz

Submission #885350

# Submission time Handle Problem Language Result Execution time Memory
885350 2023-12-09T14:03:12 Z Koyote Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 660 ms 215632 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
 
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];
vector<node*> roots; // PST
 
constexpr int lg2(const int x) { return 31 - __builtin_clz(x); }
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> k, roots.reserve(k + 1), roots.push_back(new node());
    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
    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) {
        // 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
 
    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 4 ms 25432 KB Output is correct
2 Correct 4 ms 25436 KB Output is correct
3 Correct 4 ms 27680 KB Output is correct
4 Correct 4 ms 27740 KB Output is correct
5 Correct 4 ms 27740 KB Output is correct
6 Correct 4 ms 27740 KB Output is correct
7 Correct 4 ms 27740 KB Output is correct
8 Correct 4 ms 27484 KB Output is correct
9 Correct 4 ms 27484 KB Output is correct
10 Correct 4 ms 25436 KB Output is correct
11 Correct 4 ms 25436 KB Output is correct
12 Correct 4 ms 25436 KB Output is correct
13 Correct 4 ms 27484 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25432 KB Output is correct
2 Correct 4 ms 25436 KB Output is correct
3 Correct 4 ms 27680 KB Output is correct
4 Correct 4 ms 27740 KB Output is correct
5 Correct 4 ms 27740 KB Output is correct
6 Correct 4 ms 27740 KB Output is correct
7 Correct 4 ms 27740 KB Output is correct
8 Correct 4 ms 27484 KB Output is correct
9 Correct 4 ms 27484 KB Output is correct
10 Correct 4 ms 25436 KB Output is correct
11 Correct 4 ms 25436 KB Output is correct
12 Correct 4 ms 25436 KB Output is correct
13 Correct 4 ms 27484 KB Output is correct
14 Correct 19 ms 40280 KB Output is correct
15 Correct 43 ms 55892 KB Output is correct
16 Correct 72 ms 66180 KB Output is correct
17 Correct 87 ms 73808 KB Output is correct
18 Correct 91 ms 73808 KB Output is correct
19 Correct 84 ms 73812 KB Output is correct
20 Correct 91 ms 73732 KB Output is correct
21 Correct 89 ms 72996 KB Output is correct
22 Correct 67 ms 70812 KB Output is correct
23 Correct 68 ms 67612 KB Output is correct
24 Correct 60 ms 64136 KB Output is correct
25 Correct 68 ms 71576 KB Output is correct
26 Correct 80 ms 70680 KB Output is correct
27 Correct 94 ms 71344 KB Output is correct
28 Correct 71 ms 71508 KB Output is correct
29 Correct 93 ms 73044 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25432 KB Output is correct
2 Correct 4 ms 25436 KB Output is correct
3 Correct 4 ms 27680 KB Output is correct
4 Correct 4 ms 27740 KB Output is correct
5 Correct 4 ms 27740 KB Output is correct
6 Correct 4 ms 27740 KB Output is correct
7 Correct 4 ms 27740 KB Output is correct
8 Correct 4 ms 27484 KB Output is correct
9 Correct 4 ms 27484 KB Output is correct
10 Correct 4 ms 25436 KB Output is correct
11 Correct 4 ms 25436 KB Output is correct
12 Correct 4 ms 25436 KB Output is correct
13 Correct 4 ms 27484 KB Output is correct
14 Correct 19 ms 40280 KB Output is correct
15 Correct 43 ms 55892 KB Output is correct
16 Correct 72 ms 66180 KB Output is correct
17 Correct 87 ms 73808 KB Output is correct
18 Correct 91 ms 73808 KB Output is correct
19 Correct 84 ms 73812 KB Output is correct
20 Correct 91 ms 73732 KB Output is correct
21 Correct 89 ms 72996 KB Output is correct
22 Correct 67 ms 70812 KB Output is correct
23 Correct 68 ms 67612 KB Output is correct
24 Correct 60 ms 64136 KB Output is correct
25 Correct 68 ms 71576 KB Output is correct
26 Correct 80 ms 70680 KB Output is correct
27 Correct 94 ms 71344 KB Output is correct
28 Correct 71 ms 71508 KB Output is correct
29 Correct 93 ms 73044 KB Output is correct
30 Correct 319 ms 179752 KB Output is correct
31 Correct 363 ms 189776 KB Output is correct
32 Correct 442 ms 198500 KB Output is correct
33 Correct 627 ms 215280 KB Output is correct
34 Correct 273 ms 177648 KB Output is correct
35 Correct 600 ms 215240 KB Output is correct
36 Correct 660 ms 215244 KB Output is correct
37 Correct 609 ms 215308 KB Output is correct
38 Correct 607 ms 214960 KB Output is correct
39 Correct 625 ms 215632 KB Output is correct
40 Correct 565 ms 210256 KB Output is correct
41 Correct 605 ms 215288 KB Output is correct
42 Correct 612 ms 215536 KB Output is correct
43 Correct 405 ms 207208 KB Output is correct
44 Correct 417 ms 207064 KB Output is correct
45 Correct 421 ms 207476 KB Output is correct
46 Correct 407 ms 191600 KB Output is correct
47 Correct 403 ms 180704 KB Output is correct
48 Correct 475 ms 201468 KB Output is correct
49 Correct 500 ms 201476 KB Output is correct