#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
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:154:15: warning: unused variable 'm' [-Wunused-variable]
int n, k, m;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
14584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
15336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
257 ms |
18572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
