Submission #885368

#TimeUsernameProblemLanguageResultExecution timeMemory
885368KoyoteFortune Telling 2 (JOI14_fortune_telling2)C++11
100 / 100
317 ms70816 KiB
#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 (stderr)

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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...