Submission #845991

#TimeUsernameProblemLanguageResultExecution timeMemory
845991LeonaRagingFortune Telling 2 (JOI14_fortune_telling2)C++14
100 / 100
2009 ms182092 KiB
#include<bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define SZ(val) (int)val.size() #define all(val) val.begin(), val.end() const int maxn = 6e5 + 4; int n, k, a[maxn], b[maxn], q[maxn], idx[maxn], node[maxn], L[maxn], R[maxn], bst[maxn]; vector<int> vals, que[maxn]; struct seg_tree { vector<int> t; seg_tree() { t.resize(4 * maxn); } void init() { t.clear(); t.resize(4 * maxn); } void update(int pos, int val, int v = 1, int l = 1, int r = maxn - 1) { if (l == r) { t[v] += val; return; } int m = (l + r) / 2; if (pos <= m) update(pos, val, 2 * v, l, m); else update(pos, val, 2 * v + 1, m + 1, r); t[v] = t[2 * v] + t[2 * v + 1]; } int get(int l, int r, int v = 1, int tl = 1, int tr = maxn - 1) { if (tl > r || tr < l) return 0; if (tl >= l && tr <= r) return t[v]; int m = (tl + tr) / 2; return get(l, r, 2 * v, tl, m) + get(l, r, 2 * v + 1, m + 1, tr); } } IT1; struct persistent { vector<int> t, L, R; int num; persistent() { num = 0; t.resize(1e7); L.resize(1e7); R.resize(1e7); } int update(int pos, int val, int v, int l = 1, int r = maxn - 1) { if (pos < l || pos > r) return v; if (l == r) { t[++num] = t[v] + val; return num; } int m = (l + r) / 2, cur = ++num; L[cur] = update(pos, val, L[v], l, m); R[cur] = update(pos, val, R[v], m + 1, r); t[cur] = t[L[cur]] + t[R[cur]]; return cur; } int get(int l, int r, int v, int tl = 1, int tr = maxn - 1) { if (tl > r || tr < l) return 0; if (tl >= l && tr <= r) return t[v]; int m = (tl + tr) / 2; return get(l, r, L[v], tl, m) + get(l, r, R[v], m + 1, tr); } } IT2; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen("SwapCard.INP", "r")) { freopen("SwapCard.INP", "r", stdin); freopen("SwapCard.OUT", "w", stdout); } cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i] >> b[i], idx[i] = i; vals.pb(a[i]); vals.pb(b[i]); } for (int i = 1; i <= k; i++) { cin >> q[i]; vals.pb(q[i]); } sort(all(vals)); vals.erase(unique(all(vals)), vals.end()); for (int i = 1; i <= n; i++) { a[i] = lower_bound(all(vals), a[i]) - vals.begin() + 1; b[i] = lower_bound(all(vals), b[i]) - vals.begin() + 1; } for (int i = k; i >= 1; i--) { q[i] = lower_bound(all(vals), q[i]) - vals.begin() + 1; node[i] = IT2.update(q[i], 1, node[i + 1]); } // for (int i = 1; i <= n; i++) // clog << a[i] << ' ' << b[i] << endl; // for (int i = 1; i <= k; i++) // clog << q[i] << endl; for (int i = 1; i <= n; i++) L[i] = 1, R[i] = k; for (int t = 0; t < 18; t++) { for (int i = 1; i <= n; i++) que[(L[i] + R[i]) / 2].pb(i); IT1.init(); for (int i = k; i >= 1; i--) { IT1.update(q[i], 1); // if (i == 3) clog << q[i] << ' ' << IT1.get(1, 1); for (int j : que[i]) if (IT1.get(min(a[j], b[j]), max(a[j], b[j]) - 1)) { bst[j] = i; L[j] = i + 1; } else R[j] = i - 1; que[i].clear(); } } long long res = 0; for (int i = 1; i <= n; i++) { int p = bst[i], lo = min(a[i], b[i]), hi = max(a[i], b[i]); int cnt = IT2.get(hi, SZ(vals), node[p + 1]); if (!p) res += (cnt & 1 ? vals[b[i] - 1] : vals[a[i] - 1]); else res += (cnt & 1 ? vals[lo - 1] : vals[hi - 1]); } cout << res; }

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:74:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   freopen("SwapCard.INP", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:75:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |   freopen("SwapCard.OUT", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...