#include "bits/stdc++.h"
using namespace std;
#define ar array
const int N = 2e5 + 5;
int a[N], b[N], f[N], t[N];
struct ST{
int tree[N<<2], sum[N<<2];
void init(){
memset(tree, 127, sizeof tree);
}
void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
if(lx == rx) { tree[x] = v, sum[x] = 1; return; }
int m = (lx + rx) >> 1;
if(i <= m) sett(i, v, lx, m, x<<1);
else sett(i, v, m+1, rx, x<<1|1);
tree[x] = min(tree[x<<1], tree[x<<1|1]);
sum[x] = sum[x<<1] + sum[x<<1|1];
}
int get(int a, int lx = 0, int rx = N, int x = 1){
if(lx == rx) return lx;
int m = (lx + rx) >> 1;
if(tree[x<<1] < a) return get(a, m+1, rx, x<<1|1);
return get(a, lx, m, x<<1);
}
int get_s(int l, int r, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return 0;
if(lx >= l && rx <= r) return sum[x];
int m = (lx + rx) >> 1;
return get_s(l, r, lx, m, x<<1) + get_s(l, r, m+1, rx, x<<1|1);
}
}tree;
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
tree.init();
int n, k; cin>>n>>k;
for(int i=0;i<n;i++){
cin>>a[i]>>b[i];
if(a[i] > b[i]) f[i] = 1, swap(a[i], b[i]);
}
for(int i=0;i<k;i++){
cin>>t[i];
}
vector<int> p(n); iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int i, int j) { return (a[i] > a[j]); });
vector<int> q(k); iota(q.begin(), q.end(), 0);
sort(q.begin(), q.end(), [&](int i, int j) { return (t[i] > t[j]); });
int j = 0, res = 0;
for(auto i : p){
while(j<k && t[q[j]] >= a[i]){
tree.sett(q[j], t[q[j]]);
j++;
}
int p = tree.get(b[i]);
if(a[i] <= t[p] && t[p] < b[i]){
int s = tree.get_s(p + 1, N);
if(s&1) res += a[i];
else res += b[i];
} else {
if(f[i]) swap(a[i], b[i]);
if(j&1){
res += b[i];
} else {
res += a[i];
}
}
}
cout<<res<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
