제출 #228177

#제출 시각아이디문제언어결과실행 시간메모리
228177tri운세 보기 2 (JOI14_fortune_telling2)C++14
35 / 100
815 ms166648 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pi; typedef pair<ll, ll> pl; typedef vector<int> vi; typedef vector<ld> vd; typedef vector<ll> vl; #define pb push_back #define f first #define s second static const int MAXN = 600100, NODES = 7 * MAXN; // different definition of lz to nicely implement persistence // lz is only for children, node which it is on already contains updated value int lC[NODES], rC[NODES], tr[NODES]; int nx = 0; inline int cpy(int o) { int n = nx++; lC[n] = lC[o], rC[n] = rC[o], tr[n] = tr[o]; return n; } int b(int l, int r) { if (l == r) { tr[nx] = 0; return nx++; } int mid = (l + r) / 2; lC[nx] = b(l, mid); rC[nx] = b(mid + 1, r); return nx++; } // q does not create any new nodes int q(int i, int l, int r, int s, int e) { if (e < l || r < s) { return 0; } if (s <= l && r <= e) { return tr[i]; } int mid = (l + r) / 2; return q(lC[i], l, mid, s, e) + q(rC[i], mid + 1, r, s, e); } // returns index of updated node int u(int i, int l, int r, int x, int d) { i = cpy(i); if (l == r) { tr[i] += d; return i; } int mid = (l + r) / 2; if (x <= mid) { lC[i] = u(lC[i], l, mid, x, d); } else { rC[i] = u(rC[i], mid + 1, r, x, d); } tr[i] = tr[lC[i]] + tr[rC[i]]; return i; } int N, K; pi c[MAXN]; int op[MAXN]; int rt[MAXN]; set<int> vals; map<int, int> mp; map<int, int> rMp; int nV; // search for first index with element in range int binSearch(pi range) { int low = 1; int hi = K + 1; while (low != hi) { int mid = (low + hi) / 2; if (q(rt[mid], 0, nV, range.f, range.s) > 0) { hi = mid; } else { low = mid + 1; } } return low; } int main() { cin >> N >> K; for (int i = 0; i < N; i++) { cin >> c[i].f >> c[i].s; vals.insert(c[i].f); vals.insert(c[i].s); } for (int i = 0; i < K; i++) { cin >> op[K - i]; vals.insert(op[K - i]); } nV = 0; for (int x : vals) { mp[x] = nV; rMp[nV] = x; nV++; } for (int i = 0; i < N; i++) { c[i].f = mp[c[i].f]; c[i].s = mp[c[i].s]; } for (int i = 0; i < K; i++) { op[K - i] = mp[op[K - i]]; } assert(nV <= MAXN); rt[0] = b(0, nV); for (int i = 1; i <= K; i++) { rt[i] = u(rt[i - 1], 0, nV, op[i], 1); } ll ans = 0; for (int i = 0; i < N; i++) { // ps(c[i]); int small = min(c[i].f, c[i].s); int big = max(c[i].f, c[i].s); if (small == big) { // ps("add", rMp[small]); ans += rMp[small]; continue; } int force = binSearch({small, big - 1}); // ps(force); int flip = q(rt[force - 1], 0, nV, big, nV); if (force == K + 1 && c[i].f == small) flip++; // ps(flip); if (flip & 1) { // ps("add", rMp[small]); ans += rMp[small]; } else { // ps("add", rMp[big]); ans += rMp[big]; } } cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...