Submission #28885

#TimeUsernameProblemLanguageResultExecution timeMemory
28885cdemirerFortune Telling 2 (JOI14_fortune_telling2)C++14
35 / 100
2000 ms99384 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<vector<int> > vvi; typedef vector<pair<int, int> > vii; typedef vector<vector<pair<int, int> > > vvii; #define pb(x) push_back(x) #define mp(x, y) make_pair(x, y) int twopow[22] = {0}; // x is always 2 int mypow(int x, int e) { if (twopow[e]) return twopow[e]; if (e == 0) return 1; int a = mypow(x, e/2); return (twopow[e] = (e % 2 == 0) ? a*a : a*a*x); } int N, K; vii cisimler; map<int, int> tbl; map<int, int> revtbl; int queries[200002]; vii qs; int rmqtbl[200002][19]; int rminqtbl[200002][19]; vii tickets; bool kucuk[200002]; int rmq(int a, int b) { //cerr << "max of: "; //for (int i = a; i <= b; i++) { //cerr << rmqtbl[i][0] << " "; //} int pop = b - a + 1; int e = (int)log2(pop); int a2 = b - mypow(2, e) + 1; return max(rmqtbl[a][e], rmqtbl[a2][e]); } int rminq(int a, int b) { int pop = b - a + 1; int e = (int)log2(pop); int a2 = b - mypow(2, e) + 1; return min(rminqtbl[a][e], rminqtbl[a2][e]); } int binsrc(int x) { int l = 0, r = K; while (r > l) { int mid = (l + r) / 2; if (qs[mid].first >= x) r = mid; else l = mid+1; } return l; } int bit[524289] = {0}; void bitinc(int x) { x += 2; while (x <= 524288) { bit[x]++; x += x & -x; } } int bitget(int x) { x += 2; int sum = 0; while (x > 0) { sum += bit[x]; x -= x & -x; } return sum; } int main(int argc, char **argv) { //freopen("input", "r", stdin); //freopen("output", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> K; set<int> S; for (int i = 0; i < N; i++) { int a, b; cin >> a >> b; cisimler.pb(mp(a, b)); S.insert(a); S.insert(b); } for (int i = 0; i < K; i++) { int a; cin >> a; queries[i] = a; qs.pb(mp(a, i)); S.insert(a); } int c = 0; while ( ! S.empty() ) { int x = *S.begin(); S.erase(S.begin()); tbl[x] = c; revtbl[c] = x; c++; } for (int i = 0; i < N; i++) { cisimler[i].first = tbl[cisimler[i].first]; cisimler[i].second = tbl[cisimler[i].second]; //cerr << i << " " << revtbl[cisimler[i].first] << " " << revtbl[cisimler[i].second] << "\n"; } for (int i = 0; i < K; i++) { queries[i] = tbl[queries[i]]; qs[i].first = tbl[qs[i].first]; } sort(qs.begin(), qs.end()); for (int i = 0; i < K; i++) { rmqtbl[i][0] = qs[i].second; rminqtbl[i][0] = qs[i].second; } for (int e = 1; e < 18; e++) { int off = mypow(2, e-1); for (int i = 0; i < K; i++) { if (i+2*off > K) break; rmqtbl[i][e] = max(rmqtbl[i][e-1], rmqtbl[i+off][e-1]); rminqtbl[i][e] = min(rminqtbl[i][e-1], rminqtbl[i+off][e-1]); } } for (int i = 0; i < N; i++) { int cmin = min(cisimler[i].first, cisimler[i].second); int cmax = max(cisimler[i].first, cisimler[i].second); int ls = binsrc(cmin); //cerr << cmin << endl; int hs = binsrc(cmax); if (ls == K) { kucuk[i] = (cmin == cisimler[i].first); continue; } if (hs == K) { kucuk[i] = false; continue; } //cerr << "ls : " << ls << " hs : " << hs << endl; if (ls != hs) { int q = rmq(ls, hs-1); //cerr << " is " << q << endl; tickets.pb(mp(q+1, i)); } else { int q = rminq(ls, K-1); //cerr << ls << " " << q << endl; if (cmin == cisimler[i].first) { tickets.pb(mp(q+1, i)); } else { tickets.pb(mp(q, i)); } } } /*for (int i = 0; i < tickets.size(); i++) { cerr << tickets[i].first << " " << tickets[i].second << endl; }*/ int cur = K; sort(tickets.begin(), tickets.end()); for (int i = tickets.size()-1; i >= 0; i--) { int x = tickets[i].second; while (cur > tickets[i].first) { cur--; bitinc(queries[cur]); } int lim = max(cisimler[x].first, cisimler[x].second); int a = bitget(500000) - bitget(lim-1); //if (x == 3) cerr << lim << "\n"; kucuk[x] = (a % 2 == 1); } ll sum = 0; for (int i = 0; i < N; i++) { //cerr << kucuk[i] << endl; if (kucuk[i]) { sum += revtbl[ min(cisimler[i].first, cisimler[i].second) ]; } else { sum += revtbl[ max(cisimler[i].first, cisimler[i].second) ]; } } cout << sum << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...