Submission #47672

#TimeUsernameProblemLanguageResultExecution timeMemory
47672_EmanuelNrx_Fortune Telling 2 (JOI14_fortune_telling2)C++14
0 / 100
257 ms18572 KiB
#include <bits/stdc++.h> using namespace std; const int DIM = 600005; pair<int, int> seg[DIM], num[DIM]; vector<int> aux, lst[DIM]; int sgt[DIM << 2], bit[DIM], arr[DIM], pos[DIM]; inline bool cmp(pair<int, int> sg1, pair<int, int> sg2) { return max(sg1.first, sg1.second) < max(sg2.first, sg2.second); } void update(int nod, int lef, int rig, int pos, int val) { if (lef == rig) sgt[nod] = max(sgt[nod], val); else { int mid = (lef + rig) >> 1; if (pos <= mid) update(nod << 1, lef, mid, pos, val); else update(nod << 1 | 1, mid + 1, rig, pos, val); sgt[nod] = max(sgt[nod << 1], sgt[nod << 1 | 1]); } } int query(int nod, int lef, int rig, int _lef, int _rig) { if (_lef <= lef and rig <= _rig) return sgt[nod]; else { int mid = (lef + rig) >> 1; if (_rig <= mid) return query(nod << 1, lef, mid, _lef, _rig); if (_lef > mid) return query(nod << 1 | 1, mid + 1, rig, _lef, _rig); return max(query(nod << 1, lef, mid, _lef, _rig), query(nod << 1 | 1, mid + 1, rig, _lef, _rig)); } } void update(int pos, int n) { for (int i = pos; i <= n; i += (i & -i)) bit[i] ^= 1; } int query(int pos, int x = 0) { for (int i = pos; i >= 1; i -= (i & -i)) x ^= bit[i]; return x; } long long bruteForce(int n, int k) { for (int i = 1; i <= n; ++i) cin >> seg[i].first >> seg[i].second; while (k--) { int x; cin >> x; for (int i = 1; i <= n; ++i) if (seg[i].first <= x) swap(seg[i].first, seg[i].second); } long long ans = 0; for (int i = 1; i <= n; ++i) ans += seg[i].first; return ans; } long long solve(int n, int k) { long long ans = 0; for (int i = 1; i <= n; ++i) { cin >> seg[i].first >> seg[i].second; if (seg[i].first == seg[i].second) { ans += seg[i--].first; --n; continue; } aux.push_back(seg[i].first); aux.push_back(seg[i].second); } for (int i = 1; i <= k; ++i) { cin >> pos[i]; aux.push_back(pos[i]); } sort(aux.begin(), aux.end()); aux.resize(unique(aux.begin(), aux.end()) - aux.begin()); int m = aux.size(); sort(seg + 1, seg + n + 1, cmp); for (int i = 1; i <= n; ++i) { num[i] = seg[i]; seg[i].first = lower_bound(aux.begin(), aux.end(), seg[i].first) - aux.begin() + 1; seg[i].second = lower_bound(aux.begin(), aux.end(), seg[i].second) - aux.begin() + 1; } for (int i = 1; i <= k; ++i) { pos[i] = lower_bound(aux.begin(), aux.end(), pos[i]) - aux.begin() + 1; update(1, 1, m, pos[i], i); } for (int i = 1; i <= n; ++i) { int a = seg[i].first, b = seg[i].second; if (a > b) swap(a, b); lst[query(1, 1, m, a, b - 1)].push_back(i); } for (; k >= 0; --k) { for (int x : lst[k]) { int val = query(x); if (k) val ^= (num[x].second > num[x].first); ans += val ? num[x].second : num[x].first; } int psx = 0; for (int lef = 1, rig = n; lef <= rig; ) { int mid = (lef + rig) >> 1; if (seg[mid].second <= pos[k]) lef = mid + 1, psx = mid; else rig = mid - 1; } if (psx != 0) update(1, n), update(psx + 1, n); } return ans; } int main(void) { // freopen("test.in", "r", stdin); // freopen("test.out", "w", stdout); int n, k, m; cin >> n >> k; // bool ok = true; // if (ok) // cout << bruteForce(n, k) << endl; // else cout << solve(n, k) << endl; return 0; }

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:154:15: warning: unused variable 'm' [-Wunused-variable]
     int n, k, m;
               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...