Submission #506232

#TimeUsernameProblemLanguageResultExecution timeMemory
506232colossal_pepeFortune Telling 2 (JOI14_fortune_telling2)C++17
0 / 100
1 ms1228 KiB
#include <algorithm> #include <cstring> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <iostream> #include <vector> using namespace std; using namespace __gnu_pbds; #define pow2(p) (1 << (p)) typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; int n, k; vector<int> a, b, t, flips; void makePancakes() { vector<int> t_sorted = t; sort(t_sorted.begin(), t_sorted.end()); for (int i = 0; i < n; i++) { flips[i] += t_sorted.end() - lower_bound(t_sorted.begin(), t_sorted.end(), max(a[i], b[i])); } } void adjustFlips() { vector<pair<int, int>> tp(k); for (int i = 0; i < k; i++) { tp[i].first = t[i]; tp[i].second = i; } sort(tp.begin(), tp.end()); int st[k][20]; memset(st, 0, sizeof(st)); for (int i = 0; i < k; i++) { st[i][0] = tp[i].second; } for (int j = 1; j < 20; j++) { for (int i = 0; i + pow2(j) - 1 < k; i++) { st[i][j] = max(st[i][j - 1], st[i + pow2(j - 1)][j]); } } int log2[200005]; log2[1] = 0; for (int i = 2; i < 200005; i++) { log2[i] = log2[i / 2] + 1; } vector<pair<int, int>> p(n); for (int i = 0; i < n; i++) { p[i].second = i; p[i].first = -1; int l = lower_bound(tp.begin(), tp.end(), make_pair(min(a[i], b[i]), -1)) - tp.begin(); int r = lower_bound(tp.begin(), tp.end(), make_pair(max(a[i], b[i]), -1)) - tp.begin(); if (l == r) continue; flips[i] += (b[i] > a[i]); int j = log2[r - l]; p[i].first = max(st[l][j], st[r - (1 << j)][j]); } sort(p.begin(), p.end()); int ti = 0, pi = 0; while (p[pi].first == -1) pi++; ordered_set os; while (ti < k) { os.insert({t[ti], ti}); while (pi < n and p[pi].first == ti) { flips[p[pi].second] -= os.size() - os.order_of_key({max(a[p[pi].second], b[p[pi].second]), -1}); pi++; } ti++; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> k; a.resize(n), b.resize(n), flips.resize(n); t.resize(k); for (int i = 0; i < n; i++) { cin >> a[i] >> b[i]; } for (int i = 0; i < k; i++) { cin >> t[i]; } makePancakes(); adjustFlips(); long long ans = 0; for (int i = 0; i < n; i++) { if (flips[i] % 2) ans += b[i]; else ans += a[i]; } cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...