oj.uz

Submission #885349

# Submission time Handle Problem Language Result Execution time Memory
885349 2023-12-09T14:01:02 Z Koyote Fortune Telling 2 (JOI14_fortune_telling2) C++11
100 / 100
 615 ms 222580 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
 
int lg2(int x) { return 31 - __builtin_clz(x); }
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> k, 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 = [&](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;
    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 25432 KB Output is correct
2 Correct 4 ms 25436 KB Output is correct
3 Correct 4 ms 27616 KB Output is correct
4 Correct 4 ms 27604 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 27792 KB Output is correct
8 Correct 5 ms 27740 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 25568 KB Output is correct
12 Correct 4 ms 25604 KB Output is correct
13 Correct 4 ms 27732 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25432 KB Output is correct
2 Correct 4 ms 25436 KB Output is correct
3 Correct 4 ms 27616 KB Output is correct
4 Correct 4 ms 27604 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 27792 KB Output is correct
8 Correct 5 ms 27740 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 25568 KB Output is correct
12 Correct 4 ms 25604 KB Output is correct
13 Correct 4 ms 27732 KB Output is correct
14 Correct 20 ms 40528 KB Output is correct
15 Correct 42 ms 56576 KB Output is correct
16 Correct 66 ms 66772 KB Output is correct
17 Correct 88 ms 74856 KB Output is correct
18 Correct 90 ms 74792 KB Output is correct
19 Correct 93 ms 74956 KB Output is correct
20 Correct 87 ms 75064 KB Output is correct
21 Correct 86 ms 74192 KB Output is correct
22 Correct 65 ms 71692 KB Output is correct
23 Correct 62 ms 68040 KB Output is correct
24 Correct 60 ms 64724 KB Output is correct
25 Correct 68 ms 72280 KB Output is correct
26 Correct 68 ms 71884 KB Output is correct
27 Correct 78 ms 72648 KB Output is correct
28 Correct 71 ms 72648 KB Output is correct
29 Correct 94 ms 74092 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25432 KB Output is correct
2 Correct 4 ms 25436 KB Output is correct
3 Correct 4 ms 27616 KB Output is correct
4 Correct 4 ms 27604 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 27792 KB Output is correct
8 Correct 5 ms 27740 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 25568 KB Output is correct
12 Correct 4 ms 25604 KB Output is correct
13 Correct 4 ms 27732 KB Output is correct
14 Correct 20 ms 40528 KB Output is correct
15 Correct 42 ms 56576 KB Output is correct
16 Correct 66 ms 66772 KB Output is correct
17 Correct 88 ms 74856 KB Output is correct
18 Correct 90 ms 74792 KB Output is correct
19 Correct 93 ms 74956 KB Output is correct
20 Correct 87 ms 75064 KB Output is correct
21 Correct 86 ms 74192 KB Output is correct
22 Correct 65 ms 71692 KB Output is correct
23 Correct 62 ms 68040 KB Output is correct
24 Correct 60 ms 64724 KB Output is correct
25 Correct 68 ms 72280 KB Output is correct
26 Correct 68 ms 71884 KB Output is correct
27 Correct 78 ms 72648 KB Output is correct
28 Correct 71 ms 72648 KB Output is correct
29 Correct 94 ms 74092 KB Output is correct
30 Correct 302 ms 182168 KB Output is correct
31 Correct 380 ms 192704 KB Output is correct
32 Correct 462 ms 202808 KB Output is correct
33 Correct 605 ms 221744 KB Output is correct
34 Correct 273 ms 179392 KB Output is correct
35 Correct 597 ms 221880 KB Output is correct
36 Correct 605 ms 221816 KB Output is correct
37 Correct 599 ms 221744 KB Output is correct
38 Correct 582 ms 221376 KB Output is correct
39 Correct 615 ms 222064 KB Output is correct
40 Correct 533 ms 216580 KB Output is correct
41 Correct 589 ms 222012 KB Output is correct
42 Correct 594 ms 222580 KB Output is correct
43 Correct 409 ms 213188 KB Output is correct
44 Correct 406 ms 212808 KB Output is correct
45 Correct 401 ms 212800 KB Output is correct
46 Correct 398 ms 196292 KB Output is correct
47 Correct 390 ms 185160 KB Output is correct
48 Correct 480 ms 208024 KB Output is correct
49 Correct 471 ms 208064 KB Output is correct