oj.uz

Submission #885356

# Submission time Handle Problem Language Result Execution time Memory
885356 2023-12-09T14:15:42 Z Koyote Fortune Telling 2 (JOI14_fortune_telling2) C++11
35 / 100
 3000 ms 70124 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();
        }
    }
    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 4 ms 27228 KB Output is correct
2 Correct 4 ms 27228 KB Output is correct
3 Correct 5 ms 29276 KB Output is correct
4 Correct 4 ms 29276 KB Output is correct
5 Correct 4 ms 29276 KB Output is correct
6 Correct 6 ms 29528 KB Output is correct
7 Correct 5 ms 29444 KB Output is correct
8 Correct 4 ms 29276 KB Output is correct
9 Correct 4 ms 29276 KB Output is correct
10 Correct 4 ms 27388 KB Output is correct
11 Correct 4 ms 27228 KB Output is correct
12 Correct 4 ms 27228 KB Output is correct
13 Correct 5 ms 29468 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27228 KB Output is correct
2 Correct 4 ms 27228 KB Output is correct
3 Correct 5 ms 29276 KB Output is correct
4 Correct 4 ms 29276 KB Output is correct
5 Correct 4 ms 29276 KB Output is correct
6 Correct 6 ms 29528 KB Output is correct
7 Correct 5 ms 29444 KB Output is correct
8 Correct 4 ms 29276 KB Output is correct
9 Correct 4 ms 29276 KB Output is correct
10 Correct 4 ms 27388 KB Output is correct
11 Correct 4 ms 27228 KB Output is correct
12 Correct 4 ms 27228 KB Output is correct
13 Correct 5 ms 29468 KB Output is correct
14 Correct 34 ms 38184 KB Output is correct
15 Correct 169 ms 49748 KB Output is correct
16 Correct 422 ms 56068 KB Output is correct
17 Correct 921 ms 58504 KB Output is correct
18 Correct 898 ms 58312 KB Output is correct
19 Correct 861 ms 58448 KB Output is correct
20 Correct 886 ms 58316 KB Output is correct
21 Correct 894 ms 58856 KB Output is correct
22 Correct 866 ms 58700 KB Output is correct
23 Correct 863 ms 56408 KB Output is correct
24 Correct 909 ms 54484 KB Output is correct
25 Correct 910 ms 59120 KB Output is correct
26 Correct 880 ms 58916 KB Output is correct
27 Correct 900 ms 58420 KB Output is correct
28 Correct 898 ms 58456 KB Output is correct
29 Correct 990 ms 58312 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27228 KB Output is correct
2 Correct 4 ms 27228 KB Output is correct
3 Correct 5 ms 29276 KB Output is correct
4 Correct 4 ms 29276 KB Output is correct
5 Correct 4 ms 29276 KB Output is correct
6 Correct 6 ms 29528 KB Output is correct
7 Correct 5 ms 29444 KB Output is correct
8 Correct 4 ms 29276 KB Output is correct
9 Correct 4 ms 29276 KB Output is correct
10 Correct 4 ms 27388 KB Output is correct
11 Correct 4 ms 27228 KB Output is correct
12 Correct 4 ms 27228 KB Output is correct
13 Correct 5 ms 29468 KB Output is correct
14 Correct 34 ms 38184 KB Output is correct
15 Correct 169 ms 49748 KB Output is correct
16 Correct 422 ms 56068 KB Output is correct
17 Correct 921 ms 58504 KB Output is correct
18 Correct 898 ms 58312 KB Output is correct
19 Correct 861 ms 58448 KB Output is correct
20 Correct 886 ms 58316 KB Output is correct
21 Correct 894 ms 58856 KB Output is correct
22 Correct 866 ms 58700 KB Output is correct
23 Correct 863 ms 56408 KB Output is correct
24 Correct 909 ms 54484 KB Output is correct
25 Correct 910 ms 59120 KB Output is correct
26 Correct 880 ms 58916 KB Output is correct
27 Correct 900 ms 58420 KB Output is correct
28 Correct 898 ms 58456 KB Output is correct
29 Correct 990 ms 58312 KB Output is correct
30 Execution timed out 3054 ms 70124 KB Time limit exceeded
31 Halted 0 ms 0 KB -