oj.uz

Submission #885368

# Submission time Handle Problem Language Result Execution time Memory
885368 2023-12-09T14:30:58 Z Koyote Fortune Telling 2 (JOI14_fortune_telling2) C++11
100 / 100
 317 ms 70816 KB 
#include <bits/stdc++.h>
using namespace std;

#define TASK "flip"
 
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

// Segment Tree (iterative)
template<class S, S (*op)(S, S), S (*e)()> struct segtree {
  private:
    int _n, _size, _log;
    vector<S> d;
    void updateS(int k) { d[k] = op(d[k << 1], d[k << 1 | 1]); }
    constexpr bool ineq(int x, int y, int z) const { return x <= y && y < z; }
  public:
    segtree() : segtree(0) {}
    explicit segtree(int __n) : segtree(vector<S>(__n, e())) {}
    explicit segtree(const vector<S> &v) : _n((int)v.size()) {
        _log = 31 - __builtin_clz(_n) + ((_n & -_n) != _n), _size = 1 << _log;
        d = vector<S>(_size << 1, e());
        for (int i = 0; i < _n; ++i) d[_size + i] = v[i];
        for (int i = _size - 1; i > 0; --i) updateS(i);
    }

    S query(int l, int r) { // [l, r)
        assert(ineq(0, l, r + 1) && ineq(l, r, _n + 1));
        S sml = e(), smr = e();
        for (l += _size, r += _size; l < r; l >>= 1, r >>= 1) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
        }
        return op(sml, smr);
    }
};

int op(int x, int y) { return max(x, y); }
int e() { return 0; }
// End of Segment Tree (iterative)

// 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.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);
    if (fopen(TASK ".inp", "r")) {
        freopen(TASK ".inp", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }
    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]), 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


    // Segment Tree (iterative)
    segtree<int, op, e> stree(vector<int>(t_idx, t_idx + sz(cmpr) + 1));
    auto query_max_t_idx = [&](int l, int r) -> int { return stree.query(l, r + 1); };
    // End of Segment Tree (iterative)

    // 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]];
    }
    // for (int i : ans) cout << i << ' ';
    cout << accumulate(ans.begin(), ans.end(), 0LL) << '\n';
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen(TASK ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen(TASK ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 2 ms 6876 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 2 ms 6880 KB Output is correct
13 Correct 2 ms 6876 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 2 ms 6876 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 2 ms 6880 KB Output is correct
13 Correct 2 ms 6876 KB Output is correct
14 Correct 12 ms 9420 KB Output is correct
15 Correct 31 ms 12528 KB Output is correct
16 Correct 38 ms 15868 KB Output is correct
17 Correct 52 ms 18380 KB Output is correct
18 Correct 55 ms 18420 KB Output is correct
19 Correct 58 ms 18396 KB Output is correct
20 Correct 54 ms 18552 KB Output is correct
21 Correct 49 ms 18556 KB Output is correct
22 Correct 39 ms 18200 KB Output is correct
23 Correct 39 ms 17764 KB Output is correct
24 Correct 40 ms 17572 KB Output is correct
25 Correct 41 ms 18164 KB Output is correct
26 Correct 50 ms 18480 KB Output is correct
27 Correct 74 ms 18396 KB Output is correct
28 Correct 57 ms 18452 KB Output is correct
29 Correct 108 ms 18376 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 2 ms 6876 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 2 ms 6880 KB Output is correct
13 Correct 2 ms 6876 KB Output is correct
14 Correct 12 ms 9420 KB Output is correct
15 Correct 31 ms 12528 KB Output is correct
16 Correct 38 ms 15868 KB Output is correct
17 Correct 52 ms 18380 KB Output is correct
18 Correct 55 ms 18420 KB Output is correct
19 Correct 58 ms 18396 KB Output is correct
20 Correct 54 ms 18552 KB Output is correct
21 Correct 49 ms 18556 KB Output is correct
22 Correct 39 ms 18200 KB Output is correct
23 Correct 39 ms 17764 KB Output is correct
24 Correct 40 ms 17572 KB Output is correct
25 Correct 41 ms 18164 KB Output is correct
26 Correct 50 ms 18480 KB Output is correct
27 Correct 74 ms 18396 KB Output is correct
28 Correct 57 ms 18452 KB Output is correct
29 Correct 108 ms 18376 KB Output is correct
30 Correct 124 ms 61144 KB Output is correct
31 Correct 159 ms 63864 KB Output is correct
32 Correct 203 ms 64724 KB Output is correct
33 Correct 293 ms 70804 KB Output is correct
34 Correct 116 ms 60992 KB Output is correct
35 Correct 285 ms 70696 KB Output is correct
36 Correct 302 ms 70696 KB Output is correct
37 Correct 285 ms 70676 KB Output is correct
38 Correct 285 ms 70748 KB Output is correct
39 Correct 303 ms 70816 KB Output is correct
40 Correct 291 ms 70764 KB Output is correct
41 Correct 293 ms 70800 KB Output is correct
42 Correct 297 ms 70700 KB Output is correct
43 Correct 214 ms 70488 KB Output is correct
44 Correct 212 ms 70444 KB Output is correct
45 Correct 214 ms 70444 KB Output is correct
46 Correct 219 ms 66236 KB Output is correct
47 Correct 239 ms 63412 KB Output is correct
48 Correct 317 ms 66460 KB Output is correct
49 Correct 315 ms 66652 KB Output is correct