Submission #321160

#TimeUsernameProblemLanguageResultExecution timeMemory
321160lohachoFortune Telling 2 (JOI14_fortune_telling2)C++14
100 / 100
558 ms26372 KiB
#include <bits/stdc++.h> using namespace std; using LL = long long; const int MOD = (int)1e9 + 7; const int NS = (int)6e5 + 4; int N, k; int a[NS], b[NS]; int t[NS]; vector<int> srt; int last[NS]; struct Data{ int pos, mn, num; bool operator<(const Data&r)const{ return pos > r.pos; } }que[NS]; int seg[NS * 4]; void push(int num, int s, int e, int pos, int val){ if(pos < s || pos > e) return; if(s == e){ seg[num] = val; return; } push(num * 2, s, (s + e) / 2, pos, val), push(num * 2 + 1, (s + e) / 2 + 1, e, pos, val); seg[num] = max(seg[num * 2], seg[num * 2 + 1]); } int get(int num, int s, int e, int fs, int fe){ if(fe < s || fs > e || fs > fe) return 0; if(s >= fs && e <= fe){ return seg[num]; } return max(get(num * 2, s, (s + e) / 2, fs, fe), get(num * 2 + 1, (s + e) / 2 + 1, e, fs, fe)); } struct fenwick{ vector < int > fenw; int N; fenwick(){} fenwick(int n):N(n){ fenw.resize(N); } void push(int x, int val){ for(int i = x; i < N; i += (i & -i)){ fenw[i] += val; } } int get(int x){ int rv = 0; for(int i = x; i; i -= (i & -i)){ rv += fenw[i]; } return rv; } }fen(NS); int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> N >> k; for(int i = 1; i <= N; ++i){ cin >> a[i] >> b[i]; srt.push_back(a[i]), srt.push_back(b[i]); } for(int i = 1; i <= k; ++i){ cin >> t[i]; srt.push_back(t[i]); } sort(srt.begin(), srt.end()); srt.erase(unique(srt.begin(), srt.end()), srt.end()); for(int i = 1; i <= N; ++i){ a[i] = lower_bound(srt.begin(), srt.end(), a[i]) - srt.begin() + 1; b[i] = lower_bound(srt.begin(), srt.end(), b[i]) - srt.begin() + 1; } for(int i = 1; i <= k; ++i){ t[i] = lower_bound(srt.begin(), srt.end(), t[i]) - srt.begin() + 1; last[t[i]] = i; } for(int i = 1; i <= (int)srt.size(); ++i){ push(1, 1, (int)srt.size(), i, last[i]); } for(int i = 1; i <= N; ++i){ int mn = min(a[i], b[i]), mx = max(a[i], b[i]); int pos = get(1, 1, (int)srt.size(), mn, mx - 1); que[i].pos = pos + 1, que[i].mn = mx, que[i].num = i; } sort(que + 1, que + N + 1); reverse(que + 1, que + N + 1); int j = N; LL ans = 0; for(int i = k; i >= 1; --i){ while(j && que[j].pos > i){ // cout << que[j].pos << ' ' << que[j].mn << ' ' << que[j].num << endl; int flip = fen.get((int)srt.size()) - fen.get(que[j].mn - 1); if(a[que[j].num] >= b[que[j].num]){ if(flip % 2){ ans += srt[b[que[j].num] - 1]; } else{ ans += srt[a[que[j].num] - 1]; } } else{ if(flip % 2){ ans += srt[a[que[j].num] - 1]; } else{ ans += srt[b[que[j].num] - 1]; } } --j; // cout << ans << endl; } fen.push(t[i], 1); } while(j){ // cout << que[j].pos << ' ' << que[j].mn << ' ' << que[j].num << endl; int flip = fen.get((int)srt.size()) - fen.get(que[j].mn - 1); if(a[que[j].num] >= b[que[j].num]){ if(flip % 2){ ans += srt[b[que[j].num] - 1]; } else{ ans += srt[a[que[j].num] - 1]; } } else{ if((flip % 2 && que[j].pos > 1) || (flip % 2 == 0 && que[j].pos == 1)){ ans += srt[a[que[j].num] - 1]; } else{ ans += srt[b[que[j].num] - 1]; } } --j; // cout << ans << endl; } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...