Submission #1197199

#TimeUsernameProblemLanguageResultExecution timeMemory
1197199julia_08운세 보기 2 (JOI14_fortune_telling2)C++20
100 / 100
311 ms16284 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int MAXN = 2e5 + 10; const int INF = 2e9; struct node{ int min, id; node(){ min = INF; } }; int a[MAXN], b[MAXN], t[MAXN], s[MAXN]; node seg[4 * MAXN]; int bit[3 * MAXN]; int n, k; vector<int> all_c; int ind(int x){ return lower_bound(all_c.begin(), all_c.end(), x) - all_c.begin() + 1; } void update(int x, int lx, int rx, int i, int val){ if(rx < i || lx > i) return; if(lx == rx){ seg[x].min = val; seg[x].id = lx; return; } int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1; update(lc, lx, m, i, val); update(rc, m + 1, rx, i, val); seg[x].min = min(seg[lc].min, seg[rc].min); seg[x].id = (seg[lc].min < seg[rc].min ? seg[lc].id : seg[rc].id); } pair<int, int> query(int x, int lx, int rx, int l, int r){ if(rx < l || lx > r) return {INF, INF}; if(l <= lx && rx <= r) return {seg[x].min, seg[x].id}; int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1; return min(query(lc, lx, m, l, r), query(rc, m + 1, rx, l, r)); } void bit_add(int pos, int x){ for(int i=pos; i<=(2 * n + k); i+=(i&-i)){ bit[i] += x; } } int bit_query(int pos){ int sum = 0; for(int i=pos; i>0; i-=(i&-i)){ sum += bit[i]; } return sum; } int main(){ cin.tie(0)->sync_with_stdio(0); cin >> n >> k; vector<pair<int, int>> ord; for(int i=1; i<=n; i++){ cin >> a[i] >> b[i]; if(a[i] > b[i]){ s[i] = 1; swap(a[i], b[i]); } all_c.push_back(a[i]); all_c.push_back(b[i]); ord.push_back({b[i], i}); } sort(ord.begin(), ord.end()); for(int i=1; i<=k; i++){ cin >> t[i]; all_c.push_back(t[i]); } sort(all_c.begin(), all_c.end()); all_c.erase(unique(all_c.begin(), all_c.end()), all_c.end()); for(int i=0; i<n; i++) update(1, 1, n, i + 1, a[ord[i].second]); ll ans = 0; int tot = 0; for(int i=k; i>=1; i--){ int pos = upper_bound(ord.begin(), ord.end(), make_pair(t[i], INF)) - ord.begin() + 1; if(pos > (int) ord.size()){ bit_add(ind(t[i]), 1); tot ++; continue; } int j = query(1, 1, n, pos, n).second - 1; while(j < n && a[ord[j].second] <= t[i]){ if((tot - bit_query(ind(a[ord[j].second]) - 1)) % 2 == 0){ ans += b[ord[j].second]; } else ans += a[ord[j].second]; a[ord[j].second] = INF; update(1, 1, n, j + 1, INF); j = query(1, 1, n, pos, n).second - 1; } bit_add(ind(t[i]), 1); tot ++; } for(int i=0; i<n; i++){ if(a[ord[i].second] != INF){ if(s[ord[i].second]) swap(b[ord[i].second], a[ord[i].second]); if((tot - bit_query(ind(a[ord[i].second]) - 1)) % 2 == 0){ ans += a[ord[i].second]; } else ans += b[ord[i].second]; } } cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...