#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define rep(i, a, b) for (int i = (int)a; i <= (int)b; ++i)
#define rep1(i, a, b) for (int i = (int)a; i >= (int)b; --i)
#define all(x) x.begin(), x.end()
const int N = 6e5 + 5;
struct mst{
vector<vector<int>> node;
int sz = 1;
void build(vector<int> &a, int x, int lx, int rx) {
if (rx - lx == 1) {
if (lx < a.size()) {
node[x].resize(1, a[lx]);
}
return;
}
int m = (lx + rx) >> 1;
build(a, 2 * x + 1, lx, m);
build(a, 2 * x + 2, m, rx);
merge(all(node[2 * x + 1]), all(node[2 * x + 2]), back_inserter(node[x]));
}
void init(vector<int> &a) {
int SIZE = a.size();
while (sz < SIZE) sz *= 2;
node.resize(2 * sz);
build(a, 0, 0, sz);
}
int bigger(int l, int r, int k, int x, int lx, int rx) {
if (rx <= l || r <= lx) return 0;
if (l <= lx && rx <= r) {
auto &v = node[x];
auto it = upper_bound(all(v), k);
int res = v.end() - it;
return res;
}
int m = (lx + rx) >> 1;
int s1 = bigger(l, r, k, 2 * x + 1, lx, m);
int s2 = bigger(l, r, k, 2 * x + 2, m, rx);
return s1 + s2;
}
int bigger(int l, int r, int k) {return bigger(l, r, k, 0, 0, sz);}
};
struct segtree {
int sz = 1;
vector<int> maxi;
void init(int SIZE) {
while (sz < SIZE) sz *= 2;
maxi.resize(2 * sz);
}
void update(int i, int v, int x, int lx, int rx) {
if (rx - lx == 1) {
maxi[x] = v;
return;
}
int m = (lx + rx) >> 1;
if (i < m) update(i, v, 2 * x + 1, lx, m);
else update(i, v, 2 * x + 2, m, rx);
maxi[x] = max(maxi[2 * x + 1], maxi[2 * x + 2]);
}
void update(int i, int v) {update(i, v, 0, 0, sz);}
int query(int l, int r, int x, int lx, int rx) {
if (rx <= l || r <= lx) return 0;
if (l <= lx && rx <= r) return maxi[x];
int m = (lx + rx) >> 1;
return max(query(l, r, 2 * x + 1, lx, m), query(l, r, 2 * x + 2, m, rx));
}
int query(int l, int r) {return query(l, r, 0, 0, sz);}
};
int pos[N];
void solve() {
int n, k; cin >> n >> k;
vector<int> comp;
vector<int> a(n + 1), b(n + 1), c(k + 1), sig(n + 1);
rep(i, 1, n) {
cin >> a[i] >> b[i];
sig[i] = (a[i] <= b[i]);
if (a[i] > b[i]) swap(a[i], b[i]);
comp.pb(a[i]);
comp.pb(b[i]);
}
rep(i, 1, k) {
cin >> c[i];
comp.pb(c[i]);
}
sort(all(comp));
rep(i, 1, n) {
a[i] = lower_bound(all(comp), a[i]) - comp.begin() + 1;
b[i] = lower_bound(all(comp), b[i]) - comp.begin() + 1;
}
rep(i, 1, k) {
c[i] = lower_bound(all(comp), c[i]) - comp.begin() + 1;
pos[c[i]] = max(pos[c[i]], i);
}
segtree st;
mst st1;
st1.init(c);
st.init(N + 5);
rep(i, 1, N - 1) {
st.update(i, pos[i]);
}
ll sum = 0;
rep(i, 1, n) {
int mx = st.query(a[i], b[i]);
int cnt = st1.bigger(mx + 1, k + 1, b[i] - 1);
sig[i] ^= (cnt & 1);
int res;
if (sig[i]) res = min(a[i], b[i]);
else res = max(a[i], b[i]);
res = comp[res - 1];
sum += res;
}
cout << sum;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
solve();
}
Compilation message
fortune_telling2.cpp: In member function 'void mst::build(std::vector<int>&, int, int, int)':
fortune_telling2.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | if (lx < a.size()) {
| ~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
8700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
8700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
8700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
