#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
template<class T> struct merge_sort_tree {
int _l, _r, _m;
vector<T> v;
merge_sort_tree *left, *right;
merge_sort_tree(int l, int r, vector<T> &e) {
v.resize(r - l + 1);
_l = l, _r = r, _m = (l + r) >> 1, v[0] = e[l];
if (l == r) left = right = nullptr;
else {
left = new merge_sort_tree(_l, _m, e);
right = new merge_sort_tree(_m + 1, _r, e);
vector<T> v1 = left->v, v2 = right->v;
v.clear();
int s1 = sz(v1), s2 = sz(v2);
v.reserve(s1 + s2);
int i = 0, j = 0;
while (i < s1 && j < s2) {
if (v1[i] <= v2[j]) v.push_back(v1[i]), i++;
else v.push_back(v2[j]), j++;
}
while (i < s1) v.push_back(v1[i]), i++;
while (j < s2) v.push_back(v2[j]), j++;
}
}
int count(int l, int r, T a, T b) {
if (a > b) return 0;
if (l > _r || r < _l) return 0;
if (_l >= l && _r <= r) return upper_bound(all(v), b) - lower_bound(all(v), a);
return left->count(l, r, a, b) + right->count(l, r, a, b);
}
};
const int N = 2e5 + 2, LG = 21;
int n, k, a[N], b[N], t[N], ti[N];
int spt_max_ti[N][LG];
int lg2(int x) { return x ? 31 - __builtin_clz(x) : -1; }
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
for (int i = 0; i < k; i++) cin >> t[i];
vector<int> compr; compr.reserve(2 * n + k);
for (int i = 0; i < n; i++) compr.push_back(a[i]), compr.push_back(b[i]);
for (int i = 0; i < k; i++) compr.push_back(t[i]);
sort(compr.begin(), compr.end());
compr.erase(unique(compr.begin(), compr.end()), compr.end());
for (int i = 0; i < n; i++) {
a[i] = lower_bound(compr.begin(), compr.end(), a[i]) - compr.begin();
b[i] = lower_bound(compr.begin(), compr.end(), b[i]) - compr.begin();
t[i] = lower_bound(compr.begin(), compr.end(), t[i]) - compr.begin();
}
int max_ti = *max_element(t, t + k);
for (int i = 0; i <= max_ti; i++) ti[i] = -1;
for (int i = 0; i < k; i++) ti[t[i]] = i;
for (int i = 0; i <= max_ti; i++)
spt_max_ti[i][0] = ti[i];
for (int j = 1; j < LG; j++)
for (int i = 0; i + (1 << j) - 1 <= max_ti; i++)
spt_max_ti[i][j] = max(spt_max_ti[i][j - 1], spt_max_ti[i + (1 << (j - 1))][j - 1]);
auto query_max_ti = [&](int l, int r) {
int len = lg2(r - l + 1);
return max(spt_max_ti[l][len], spt_max_ti[r - (1 << len) + 1][len]);
};
vector<int> t_vector(k);
for (int i = 0; i < k; i++) t_vector[i] = t[i];
auto cnt_in_range_ab = merge_sort_tree<int>(0, k - 1, t_vector);
long long ans = 0;
for (int i = 0; i < n; i++) {
if (a[i] == b[i]) { ans += compr[a[i]]; continue; }
bool swapped = (a[i] > b[i]);
if (a[i] > b[i]) swap(a[i], b[i]);
auto last_pos = query_max_ti(a[i], b[i] - 1);
int cnt_flipped = cnt_in_range_ab.count(last_pos + 1, k - 1, b[i], int(1e9));
int final_faceup = (cnt_flipped + swapped) % 2;
if (final_faceup == 0) ans += compr[a[i]];
else ans += compr[b[i]];
}
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
436 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
436 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
436 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
