oj.uz

Submission #885358

# Submission time Handle Problem Language Result Execution time Memory
885358 2023-12-09T14:18:19 Z Koyote Fortune Telling 2 (JOI14_fortune_telling2) C++11
100 / 100
 310 ms 105140 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

// Merge Sort Tree
template<class T> struct merge_sort_tree {
    int _l, _r, _m;
    vector<T> v;
    merge_sort_tree *lt, *rt;
    merge_sort_tree(int l, int r, const vector<T> &e) : _l(l), _r(r), _m((l + r) >> 1) {
        v.resize(r - l + 1), v[0] = e[l];
        if (l == r) lt = rt = nullptr;
        else {
            lt = new merge_sort_tree(_l, _m, e);
            rt = new merge_sort_tree(_m + 1, _r, e);
            vector<T> v1 = lt->v, v2 = rt->v;
            // v.clear(), v.reserve(v1.size() + v2.size());
            // int i = 0, j = 0;
            // while (i < sz(v1) && j < sz(v2)) v.push_back(v1[i] <= v2[j] ? v1[i++] : v2[j++]);
            // while (i < sz(v1)) v.push_back(v1[i++]);
            // while (j < sz(v2)) v.push_back(v2[j++]);
            // v.shrink_to_fit();
            v.resize(v1.size() + v2.size());
            merge(all(v1), all(v2), v.begin());
        }
    }
    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 lt->count(l, r, a, b) + rt->count(l, r, a, b);
    }
};
// End of Merge Sort Tree
 
const int N = 2e5 + 7, N2 = 6e5 + 2, LG = 20;
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]);
 

    // Sparse table
    for (int i = 1; i <= k; i++) t_idx[t[i]] = i;
    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


    // Merge Sort Tree
    merge_sort_tree<int> mst(0, k + 1, vector<int>(t, t + k + 1));

    // Number of i that (l <= i <= r) and (x <= a[i] <= y)
    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 27228 KB Output is correct
2 Correct 4 ms 27228 KB Output is correct
3 Correct 4 ms 29264 KB Output is correct
4 Correct 4 ms 29276 KB Output is correct
5 Correct 4 ms 29192 KB Output is correct
6 Correct 4 ms 29276 KB Output is correct
7 Correct 5 ms 29276 KB Output is correct
8 Correct 4 ms 29272 KB Output is correct
9 Correct 4 ms 29276 KB Output is correct
10 Correct 4 ms 27228 KB Output is correct
11 Correct 4 ms 27276 KB Output is correct
12 Correct 4 ms 27228 KB Output is correct
13 Correct 5 ms 29276 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 27228 KB Output is correct
2 Correct 4 ms 27228 KB Output is correct
3 Correct 4 ms 29264 KB Output is correct
4 Correct 4 ms 29276 KB Output is correct
5 Correct 4 ms 29192 KB Output is correct
6 Correct 4 ms 29276 KB Output is correct
7 Correct 5 ms 29276 KB Output is correct
8 Correct 4 ms 29272 KB Output is correct
9 Correct 4 ms 29276 KB Output is correct
10 Correct 4 ms 27228 KB Output is correct
11 Correct 4 ms 27276 KB Output is correct
12 Correct 4 ms 27228 KB Output is correct
13 Correct 5 ms 29276 KB Output is correct
14 Correct 15 ms 37720 KB Output is correct
15 Correct 27 ms 48628 KB Output is correct
16 Correct 40 ms 53340 KB Output is correct
17 Correct 52 ms 55892 KB Output is correct
18 Correct 52 ms 55736 KB Output is correct
19 Correct 51 ms 55888 KB Output is correct
20 Correct 55 ms 55900 KB Output is correct
21 Correct 49 ms 55836 KB Output is correct
22 Correct 41 ms 55888 KB Output is correct
23 Correct 41 ms 53716 KB Output is correct
24 Correct 41 ms 51796 KB Output is correct
25 Correct 41 ms 55888 KB Output is correct
26 Correct 55 ms 55864 KB Output is correct
27 Correct 74 ms 55892 KB Output is correct
28 Correct 54 ms 55888 KB Output is correct
29 Correct 114 ms 55892 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 27228 KB Output is correct
2 Correct 4 ms 27228 KB Output is correct
3 Correct 4 ms 29264 KB Output is correct
4 Correct 4 ms 29276 KB Output is correct
5 Correct 4 ms 29192 KB Output is correct
6 Correct 4 ms 29276 KB Output is correct
7 Correct 5 ms 29276 KB Output is correct
8 Correct 4 ms 29272 KB Output is correct
9 Correct 4 ms 29276 KB Output is correct
10 Correct 4 ms 27228 KB Output is correct
11 Correct 4 ms 27276 KB Output is correct
12 Correct 4 ms 27228 KB Output is correct
13 Correct 5 ms 29276 KB Output is correct
14 Correct 15 ms 37720 KB Output is correct
15 Correct 27 ms 48628 KB Output is correct
16 Correct 40 ms 53340 KB Output is correct
17 Correct 52 ms 55892 KB Output is correct
18 Correct 52 ms 55736 KB Output is correct
19 Correct 51 ms 55888 KB Output is correct
20 Correct 55 ms 55900 KB Output is correct
21 Correct 49 ms 55836 KB Output is correct
22 Correct 41 ms 55888 KB Output is correct
23 Correct 41 ms 53716 KB Output is correct
24 Correct 41 ms 51796 KB Output is correct
25 Correct 41 ms 55888 KB Output is correct
26 Correct 55 ms 55864 KB Output is correct
27 Correct 74 ms 55892 KB Output is correct
28 Correct 54 ms 55888 KB Output is correct
29 Correct 114 ms 55892 KB Output is correct
30 Correct 127 ms 99000 KB Output is correct
31 Correct 162 ms 101452 KB Output is correct
32 Correct 199 ms 101836 KB Output is correct
33 Correct 279 ms 104888 KB Output is correct
34 Correct 124 ms 99100 KB Output is correct
35 Correct 275 ms 104788 KB Output is correct
36 Correct 276 ms 104768 KB Output is correct
37 Correct 283 ms 105024 KB Output is correct
38 Correct 261 ms 104764 KB Output is correct
39 Correct 295 ms 104728 KB Output is correct
40 Correct 263 ms 104792 KB Output is correct
41 Correct 271 ms 104868 KB Output is correct
42 Correct 287 ms 104764 KB Output is correct
43 Correct 204 ms 104876 KB Output is correct
44 Correct 216 ms 105140 KB Output is correct
45 Correct 207 ms 104764 KB Output is correct
46 Correct 200 ms 102820 KB Output is correct
47 Correct 238 ms 100832 KB Output is correct
48 Correct 310 ms 102836 KB Output is correct
49 Correct 286 ms 102972 KB Output is correct