#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pp;
const int N = 2e5+10;
const int X = 3*N;
int x[N], y[N], a[N], b[N], t[N], n, k;
struct segtree {
vector<int> t;
void init(int sz) {
t.resize(4*sz+1);
}
void upd(int v, int l, int r, int p, int vl) {
if (l == r) {
t[v]=max(vl, t[v]);
return;
} int m=(l+r)/2;
if (p <= m) upd(2*v, l, m, p, vl);
else upd(2*v+1, m+1, r, p, vl);
t[v]=max(t[2*v], t[2*v+1]);
}
int que(int v, int l, int r, int ql, int qr) {
if (l > qr || r < ql) return 0;
if (l >= ql && r <= qr) return t[v];
int m=(l+r)/2;
return max(que(2*v, l, m, ql, qr), que(2*v+1, m+1, r, ql, qr));
}
};
struct fenwick {
vector<int> bit;
int n;
void init(int sz) {
n=sz+10;
bit.assign(n, 0);
}
int sum(int r) {
int res=0;
for (;r>=0; r=(r&(r+1))-1) res+=bit[r];
return res;
}
int que(int l, int r) {
return sum(r)-sum(l-1);
}
void upd(int x, int d) {
for (; x<n; x=x|(x+1)) bit[x]+=d;
}
};
void solve() {
cin>>n>>k;
map<int, int> sc, resc;
set<int> st;
for (int i=1; i<=n; ++i) {
cin>>x[i]>>y[i];
st.insert(x[i]), st.insert(y[i]);
}
for (int i=1; i<=k; ++i) {
cin>>t[i];
st.insert(t[i]);
}
int i=1;
for (auto u : st) sc[u]=i, resc[i++]=u;
for (int i=1; i<=n; ++i) {
x[i]=sc[x[i]], y[i]=sc[y[i]];
a[i]=min(x[i], y[i]), b[i]=max(x[i], y[i]);
}
segtree tr; tr.init(X+10);
for (int i=1; i<=k; ++i) t[i]=sc[t[i]], tr.upd(1, 1, X, t[i], i);
vector<pp> v;
for (int i=1; i<=n; ++i) {
int j=tr.que(1, 1, X, a[i], b[i]-1);
v.push_back({b[i], {-(j+1), i}});
}
for (int i=1; i<=k; ++i) v.push_back({t[i], {i, 0}});
sort(v.begin(), v.end(), greater<pp>());
fenwick fw; fw.init(X);
ll ans=0;
for (auto u : v) {
if (u.second.first < 0) {
int j=-u.second.first;
int vv=fw.que(j, n);
int vl;
if (j == 1) {
if (vv%2) vl=b[u.second.second];
else vl=a[u.second.second];
} else {
if (vv%2) vl=a[u.second.second];
else vl=b[u.second.second];
} ans+=resc[vl];
} else {
fw.upd(u.second.first, 1);
}
} cout<<ans<<"\n";
}
int main() {
int t=1; //cin>>t;
while (t--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
14424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
14424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
14424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
