#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
pair<int, int> a[200001];
int t[200001], segtree[2400001], bit[600001];
vector<pair<int, int>> c;
bool inv[200001], visited[200001];
void build(int node = 1, int l = 1, int r = c.size()) {
if (l == r) segtree[node] = c[l - 1].second ? 0 : l;
else {
int mid = (l + r) / 2;
build(node * 2, l, mid);
build(node * 2 + 1, mid + 1, r);
segtree[node] = max(segtree[node * 2], segtree[node * 2 + 1]);
}
}
int rmq(int x, int y, int node = 1, int l = 1, int r = c.size()) {
if (l > y || r < x) return 0;
if (l >= x && r <= y) return segtree[node];
int mid = (l + r) / 2;
return max(rmq(x, y, node * 2, l, mid), rmq(x, y, node * 2 + 1, mid + 1, r));
}
void add(int pos) { for (; pos <= c.size(); pos += (pos & (-pos))) bit[pos]++; }
int rsq(int x, int y) {
int ans = 0;
for (; y; y -= (y & (-y))) ans += bit[y];
for (x--; x; x -= (x & (-x))) ans -= bit[x];
return ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
FOR(i, 1, n + 1) {
cin >> a[i].first >> a[i].second;
inv[i] = a[i].first < a[i].second;
if (inv[i]) swap(a[i].first, a[i].second);
c.push_back({a[i].first, i});
c.push_back({a[i].second, -i});
}
FOR(i, 1, q + 1) {
cin >> t[i];
c.push_back({t[i], 0});
}
sort(c.begin(), c.end());
c.erase(unique(c.begin(), c.end()), c.end());
build();
FOR(i, 1, n + 1) {
a[i].first = lower_bound(c.begin(), c.end(), make_pair(a[i].first, i)) - c.begin() + 1;
a[i].second = lower_bound(c.begin(), c.end(), make_pair(a[i].second, -i)) - c.begin() + 1;
}
// for (pair<int, int> i : c) cout << i.first << ' ' << i.second << " | ";
// cout << '\n';
// FOR(i, 1, c.size() + 1) cout << rmq(i, i) << ' ';
// cout << '\n';
ll ans = 0;
for (int i = c.size() - 1; i; i--) {
int k = c[i].second;
if (k) {
if (visited[abs(k)]) continue;
visited[k] = true;
int cnt = rsq(rmq(a[k].second, a[k].first) + 1, c.size());
// cout << cnt - inv[k] << ' ' << k << " HERE\n";
// cout << a[k].second << ' ' << a[k].first << ' ' << rmq(a[k].second, a[k].first) << '\n';
if (cnt & 1) ans += c[a[k].first - 1].first;
else ans += c[a[k].second - 1].first;
// cout << ans << '\n';
} else add(i);
}
cout << ans;
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'void add(int)':
fortune_telling2.cpp:28:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
void add(int pos) { for (; pos <= c.size(); pos += (pos & (-pos))) bit[pos]++; }
~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
