#include <bits/stdc++.h>
using namespace std;
void setup()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
class SEGMENT_TREE
{
private:
int tree_size;
vector<vector<int>> tree;
vector<int> base;
inline void Build(int ind, int l, int r)
{
if (l == r)
{
tree[ind] = {base[l]};
return;
}
int m = (l + r) >> 1;
Build(ind << 1, l, m);
Build(ind << 1 | 1, m + 1, r);
tree[ind].resize(r - l + 1);
merge(tree[ind << 1].begin(), tree[ind << 1].end(),
tree[ind << 1 | 1].begin(), tree[ind << 1 | 1].end(),
tree[ind].begin());
}
inline pair<int, int> Get(int ind, int l, int r, int x, int y)
{
int a = lower_bound(tree[ind].begin(), tree[ind].end(), x) - tree[ind].begin();
int b = lower_bound(tree[ind].begin(), tree[ind].end(), y) - tree[ind].begin();
if (a == b)
{
return {0, tree[ind].size() - b};
}
if (l == r)
{
return {1, 0};
}
int m = (l + r) >> 1;
pair<int, int> rt = Get(ind << 1 | 1, m + 1, r, x, y);
if (rt.first)
{
return rt;
}
pair<int, int> lt = Get(ind << 1, l, m, x, y);
return make_pair(lt.first, lt.second ^ rt.second);
}
public:
inline void Init(vector<int> inp)
{
base = inp;
tree_size = inp.size();
tree.clear();
tree.resize(tree_size << 2);
base.insert(base.begin(), 0);
Build(1, 1, tree_size);
}
inline pair<int, int> Get(int x, int y)
{
return Get(1, 1, tree_size, x, y);
}
} st;
int n, k, a[200000], b[200000];
vector<int> t;
pair<int, int> r;
long long res = 0;
int main()
{
setup();
cin >> n >> k;
t.resize(k);
for (int i = 0; i < n; ++i)
{
cin >> a[i] >> b[i];
}
for (int i = 0; i < k; ++i)
{
cin >> t[i];
}
st.Init(t);
r = st.Get(1, 9);
for (int i = 0; i < n; ++i)
{
r = st.Get(min(a[i], b[i]), max(a[i], b[i]));
if (r.first && a[i] < b[i])
{
swap(a[i], b[i]);
}
res += (r.second & 1 ? b[i] : a[i]);
}
cout << res;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |