Submission #885387

#	Time	Username	Problem	Language	Result	Execution time	Memory
885387		Koyote	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	100 / 100	327 ms	66092 KiB

fortune_telling2

#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 {
    int _n, _size, _log;
    vector<S> d;
    void updateS(int k) { d[k] = op(d[k << 1], d[k << 1 | 1]); }
    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)
        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 max_op(int x, int y) { return max(x, y); }
int max_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(r - l + 1) {
        if (l == r) v[0] = e[l], 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;
            merge(all(v1), all(v2), v.begin());
        }
    }
    int count(int qs, int qe, T x, T y) {
        if (x > y || _r < qs || qe < _l) return 0;
        if (qs <= _l && _r <= qe) return upper_bound(all(v), y) - lower_bound(all(v), x);
        // return lt->count(qs, qe, x, y) + rt->count(qs, qe, x, y);
        return (qs <= lt->_r ? lt->count(qs, qe, x, y) : 0) + (qe >= rt->_l ? rt->count(qs, qe, x, y) : 0);
    }
};
// End of Merge Sort Tree
 
const int N = 2e5 + 2;
int a[N], b[N], t[N], t_idx[N * 3];
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    if (fopen(TASK ".inp", "r")) {
        freopen(TASK ".inp", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }
    int n, k; 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];

    // Compressing values
    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;

    // Data Structures
    segtree<int, max_op, max_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); };

    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);
    };

    // Solving
    basic_string<int> ans; ans.reserve(n);
    for (int i = 1; i <= n; i++) {
        if (a[i] == b[i]) { ans += cmpr[a[i]]; continue; }

        // Assuming a[i] < b[i], find the last query that flips into b[i]
        bool swapped = (a[i] > b[i] ? (swap(a[i], b[i]), true) : false);
        int last_query = query_max_t_idx(a[i], b[i] - 1);

        // Count number of queries that guanrantee to flip
        int cnt_flipped = cnt_on_range(last_query + 1, k, b[i], sz(cmpr));
 
        if (last_query != 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 (stderr)

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

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65