#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
// Merge Sort Tree
template<class T> struct merge_sort_tree {
int _l, _r, _m;
vector<T> v;
merge_sort_tree *lt, *rt;
merge_sort_tree(int l, int r, const vector<T> e) : _l(l), _r(r), _m((l + r) >> 1) {
v.resize(r - l + 1), v[0] = e[l];
if (l == r) lt = rt = nullptr;
else {
lt = new merge_sort_tree(_l, _m, e);
rt = new merge_sort_tree(_m + 1, _r, e);
vector<T> v1 = lt->v, v2 = rt->v;
v.clear(), v.reserve(v1.size() + v2.size());
int i = 0, j = 0;
while (i < sz(v1) && j < sz(v2)) v.push_back(v1[i] <= v2[j] ? v1[i++] : v2[j++]);
while (i < sz(v1)) v.push_back(v1[i++]);
while (j < sz(v2)) v.push_back(v2[j++]);
v.shrink_to_fit();
}
}
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 lt->count(l, r, a, b) + rt->count(l, r, a, b);
}
};
// End of Merge Sort Tree
const int N = 2e5 + 7, N2 = 6e5 + 2, LG = 20;
int n, k, a[N], b[N], t[N], t_idx[N2], max_t_idx[LG][N2];
constexpr int lg2(const int x) { return 31 - __builtin_clz(x); }
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
for (int i = 1; i <= k; i++) cin >> t[i];
basic_string<int> cmpr; cmpr.reserve(2 * n + k + 1), cmpr += 0;
for (int i = 1; i <= n; i++) cmpr += a[i], cmpr += b[i];
for (int i = 1; i <= k; i++) cmpr += t[i];
sort(all(cmpr)), cmpr.erase(unique(all(cmpr)), cmpr.end());
auto search = [&](const int v) -> int { return lower_bound(all(cmpr), v) - cmpr.begin(); };
for (int i = 1; i <= n; i++) a[i] = search(a[i]), b[i] = search(b[i]);
for (int i = 1; i <= k; i++) t[i] = search(t[i]);
// Sparse table
for (int i = 1; i <= k; i++) t_idx[t[i]] = i;
for (int i = 1; i <= sz(cmpr); i++)
max_t_idx[0][i] = t_idx[i];
for (int j = 1; j < LG; j++)
for (int i = 1; i + (1 << j) - 1 <= sz(cmpr); i++)
max_t_idx[j][i] = max(max_t_idx[j - 1][i], max_t_idx[j - 1][i + (1 << (j - 1))]);
auto query_max_t_idx = [&](int l, int r) -> int {
int len = lg2(r - l + 1);
return max(max_t_idx[len][l], max_t_idx[len][r - (1 << len) + 1]);
};
// End of Sparse table
// Merge Sort Tree
merge_sort_tree<int> mst(0, k + 1, vector<int>(t, t + k + 1));
// Number of i that (l <= i <= r) and (x <= a[i] <= y)
auto cnt_on_range = [&](int l, int r, int x, int y) -> int {
return mst.count(l, r, x, y);
};
// End of Merge Sort Tree
basic_string<int> ans; ans.reserve(n);
for (int i = 1; i <= n; i++) {
if (a[i] == b[i]) { ans += cmpr[a[i]]; continue; }
bool swapped = (a[i] > b[i] ? (swap(a[i], b[i]), true) : false);
int last_pos = query_max_t_idx(a[i], b[i] - 1);
int cnt_flipped = cnt_on_range(last_pos + 1, k, b[i], sz(cmpr));
if (last_pos != 0 || swapped) swap(a[i], b[i]);
ans += cmpr[~cnt_flipped & 1 ? a[i] : b[i]];
}
cout << accumulate(ans.begin(), ans.end(), 0LL) << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
27228 KB |
Output is correct |
2 |
Correct |
4 ms |
27228 KB |
Output is correct |
3 |
Correct |
5 ms |
29276 KB |
Output is correct |
4 |
Correct |
4 ms |
29276 KB |
Output is correct |
5 |
Correct |
4 ms |
29276 KB |
Output is correct |
6 |
Correct |
6 ms |
29528 KB |
Output is correct |
7 |
Correct |
5 ms |
29444 KB |
Output is correct |
8 |
Correct |
4 ms |
29276 KB |
Output is correct |
9 |
Correct |
4 ms |
29276 KB |
Output is correct |
10 |
Correct |
4 ms |
27388 KB |
Output is correct |
11 |
Correct |
4 ms |
27228 KB |
Output is correct |
12 |
Correct |
4 ms |
27228 KB |
Output is correct |
13 |
Correct |
5 ms |
29468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
27228 KB |
Output is correct |
2 |
Correct |
4 ms |
27228 KB |
Output is correct |
3 |
Correct |
5 ms |
29276 KB |
Output is correct |
4 |
Correct |
4 ms |
29276 KB |
Output is correct |
5 |
Correct |
4 ms |
29276 KB |
Output is correct |
6 |
Correct |
6 ms |
29528 KB |
Output is correct |
7 |
Correct |
5 ms |
29444 KB |
Output is correct |
8 |
Correct |
4 ms |
29276 KB |
Output is correct |
9 |
Correct |
4 ms |
29276 KB |
Output is correct |
10 |
Correct |
4 ms |
27388 KB |
Output is correct |
11 |
Correct |
4 ms |
27228 KB |
Output is correct |
12 |
Correct |
4 ms |
27228 KB |
Output is correct |
13 |
Correct |
5 ms |
29468 KB |
Output is correct |
14 |
Correct |
34 ms |
38184 KB |
Output is correct |
15 |
Correct |
169 ms |
49748 KB |
Output is correct |
16 |
Correct |
422 ms |
56068 KB |
Output is correct |
17 |
Correct |
921 ms |
58504 KB |
Output is correct |
18 |
Correct |
898 ms |
58312 KB |
Output is correct |
19 |
Correct |
861 ms |
58448 KB |
Output is correct |
20 |
Correct |
886 ms |
58316 KB |
Output is correct |
21 |
Correct |
894 ms |
58856 KB |
Output is correct |
22 |
Correct |
866 ms |
58700 KB |
Output is correct |
23 |
Correct |
863 ms |
56408 KB |
Output is correct |
24 |
Correct |
909 ms |
54484 KB |
Output is correct |
25 |
Correct |
910 ms |
59120 KB |
Output is correct |
26 |
Correct |
880 ms |
58916 KB |
Output is correct |
27 |
Correct |
900 ms |
58420 KB |
Output is correct |
28 |
Correct |
898 ms |
58456 KB |
Output is correct |
29 |
Correct |
990 ms |
58312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
27228 KB |
Output is correct |
2 |
Correct |
4 ms |
27228 KB |
Output is correct |
3 |
Correct |
5 ms |
29276 KB |
Output is correct |
4 |
Correct |
4 ms |
29276 KB |
Output is correct |
5 |
Correct |
4 ms |
29276 KB |
Output is correct |
6 |
Correct |
6 ms |
29528 KB |
Output is correct |
7 |
Correct |
5 ms |
29444 KB |
Output is correct |
8 |
Correct |
4 ms |
29276 KB |
Output is correct |
9 |
Correct |
4 ms |
29276 KB |
Output is correct |
10 |
Correct |
4 ms |
27388 KB |
Output is correct |
11 |
Correct |
4 ms |
27228 KB |
Output is correct |
12 |
Correct |
4 ms |
27228 KB |
Output is correct |
13 |
Correct |
5 ms |
29468 KB |
Output is correct |
14 |
Correct |
34 ms |
38184 KB |
Output is correct |
15 |
Correct |
169 ms |
49748 KB |
Output is correct |
16 |
Correct |
422 ms |
56068 KB |
Output is correct |
17 |
Correct |
921 ms |
58504 KB |
Output is correct |
18 |
Correct |
898 ms |
58312 KB |
Output is correct |
19 |
Correct |
861 ms |
58448 KB |
Output is correct |
20 |
Correct |
886 ms |
58316 KB |
Output is correct |
21 |
Correct |
894 ms |
58856 KB |
Output is correct |
22 |
Correct |
866 ms |
58700 KB |
Output is correct |
23 |
Correct |
863 ms |
56408 KB |
Output is correct |
24 |
Correct |
909 ms |
54484 KB |
Output is correct |
25 |
Correct |
910 ms |
59120 KB |
Output is correct |
26 |
Correct |
880 ms |
58916 KB |
Output is correct |
27 |
Correct |
900 ms |
58420 KB |
Output is correct |
28 |
Correct |
898 ms |
58456 KB |
Output is correct |
29 |
Correct |
990 ms |
58312 KB |
Output is correct |
30 |
Execution timed out |
3054 ms |
70124 KB |
Time limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |