#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'
const int INF = 1e18;
struct FenwickTree{
vector<int> a; int n, s;
FenwickTree(int N){ a.resize((n=N)+1); }
void add(int i){
for(++i; i<=n; i+=i&-i) a[i] = a[i] ^ 1;
}
bool get(int i){
for(s=0; i>=1; i-=i&-i) s ^= a[i];
return s;
}
bool get(int i, int j){ return get(j+1) ^ get(i); }
};
struct SegmentTree{
vector<int> a; int sz = 1;
SegmentTree(vector<int> &v){
while(sz < (int)v.size()) sz += sz;
a.assign(2*sz, -1);
build(v, 0, 0, sz);
}
void build(vector<int> &v, int x, int lx, int rx){
if(rx-lx==1){
if(lx < (int)v.size()) a[x] = v[lx];
return;
}
int mx = (lx + rx) / 2;
build(v, 2*x+1, lx, mx);
build(v, 2*x+2, mx, rx);
a[x] = max(a[2*x+1], a[2*x+2]);
}
void update(int i, int v, int x, int lx, int rx){
if(rx-lx==1) return void(a[x] = v);
int mx = (lx + rx) / 2;
if(i < mx) update(i, v, 2*x+1, lx, mx);
else update(i, v, 2*x+2, mx, rx);
a[x] = max(a[2*x+1], a[2*x+2]);
}
void update(int i, int v){ update(i, v, 0, 0, sz); }
int lastGreater(int v, int x, int lx, int rx){
if(rx-lx==1) return lx;
int mx = (lx + rx) / 2;
if(a[2*x+2] >= v) return lastGreater(v, 2*x+2, mx, rx);
else return lastGreater(v, 2*x+1, lx, mx);
}
int lastGreater(int v){ return lastGreater(v, 0, 0, sz); }
};
signed main(){
cin.tie(0)->sync_with_stdio(0);
int n, k; cin >> n >> k;
array<int, 2> a[n], s[k];
for(auto &i : a) cin >> i[0] >> i[1];
vector<int> b(k);
for(int i=0; i<k; ++i) cin >> b[i], s[i] = {b[i], i};
sort(s, s+k);
int p = k, res = 0;
sort(a, a+n, [&](array<int, 2> &x, array<int, 2> &y){
return max(x[0], x[1]) > max(y[0], y[1]);
});
SegmentTree st(b);
FenwickTree f(k);
for(auto &i : a){
int x = i[0], y = i[1];
if(x > y) swap(x, y);
while(p && s[p-1][0] >= y){
--p;
st.update(s[p][1], -1);
f.add(s[p][1]);
}
int j = st.lastGreater(x);
if(j >= k || b[j] < x) res += i[0];
else{
if(i[0] > i[1]) swap(i[0], i[1]);
res += i[f.get(j+1, k-1) ^ 1];
}
}
cout << res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
