Submission #39466

#TimeUsernameProblemLanguageResultExecution timeMemory
39466Noam527Fortune Telling 2 (JOI14_fortune_telling2)C++14
0 / 100
453 ms262144 KiB
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <string> #include <time.h> #include <stack> #include <queue> #include <random> #include <fstream> #define endl '\n' #define flush fflush(stdout), cout.flush() #define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define debug cout << "ok" << endl #define finish(x) return cout << x << endl, 0 typedef long long ll; typedef long double ldb; const int md = 1e9 + 7; const ll hs = 199; const ldb eps = 1e-9, pi = acos(-1); using namespace std; const int maxn = 200002; struct wavelet { int lo, hi; vector<int> pr; wavelet *l = 0, *r = 0; wavelet(int *le, int *ri, int x, int y) { lo = x, hi = y; if (le < ri && lo < hi) { int mid = lo + (hi - lo) / 2; auto f = [&mid](int x) { return x <= mid; }; pr.reserve(ri - le + 1); pr.push_back(0); for (int *i = le; i != ri; i++) pr.push_back(pr.back() + f(*i)); int *piv = stable_partition(le, ri, f); l = new wavelet(le, piv, x, mid), r = new wavelet(piv, ri, mid + 1, y); } } // count greater/equals than k in [l, r] int cge(int l, int r, int k) { if (l > r || hi < k) return 0; if (lo >= k) return r - l + 1; int le = pr[l - 1], ri = pr[r]; return this->l->cge(le + 1, ri, k) + this->r->cge(l - le, r - ri, k); } }; struct sparse { int n; vector<int> tree; sparse(const int a[maxn], int size) { n = size; tree.resize(2 * n); for (int i = 0; i < n; i++) tree[i + n - 1] = a[i]; for (int i = n - 2; i >= 0; i--) tree[i] = max(tree[2 * i + 1], tree[2 * i + 2]); } int query(int l, int r) { int rtn = -1e9; for (l += n - 1, r += n - 1; l < r; l = (l - 1) / 2, r = (r - 1) / 2) { if (!(l & 1)) rtn = max(rtn, tree[l++]); if (r & 1) rtn = max(rtn, tree[r--]); } if (l == r) rtn = max(rtn, tree[l]); return rtn; } }; int n, k, a[2][maxn], b[maxn], bb[maxn], c[maxn]; ll ans = 0; bool cmp(const int &x, const int &y) { return b[x] < b[y]; } int lowerbound(const int &x) { static int lo, hi, mid; lo = 0, hi = n - 1; while (lo < hi) { mid = (lo + hi) >> 1; if (b[c[mid]] < x) lo = mid + 1; else hi = mid; } if (b[c[lo]] < x) lo++; return lo; } int main() { fast; cin >> n >> k; for (int i = 0; i < n; i++) cin >> a[0][i] >> a[1][i]; for (int i = 0; i < k; i++) cin >> b[i]; for (int i = 0; i < k; i++) c[i] = i; sort(c, c + k, cmp); sparse sp = sparse(c, k); for (int i = 0; i < maxn; i++) bb[i] = b[i]; wavelet w = wavelet(b, b + k, 1, 1e9); for (int i = 0; i < maxn; i++) b[i] = bb[i]; for (int i = 0, mn, mx, lo, hi; i < n; i++) { mn = min(a[0][i], a[1][i]); mx = max(a[0][i], a[1][i]); lo = lowerbound(mn), hi = lowerbound(mx) - 1; if (lo > hi) ans += a[w.cge(1, k, mx) & 1][i]; else ans += a[w.cge(sp.query(lo, hi) + 2, k, mx) & 1][i]; } cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...