#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(1e9 + 21071997)
using namespace std;
template<class T1, class T2>
bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}
template<class T1, class T2>
bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
template<class T1, class T2>
void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}
template<class T1, class T2>
void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}
template<class T>
void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
struct seg{
vector<int> val;
int n;
seg(int _n = 0){
n = _n;
val.resize(n * 4 + 3, 0);
}
void upd(int p, int c){
int i = 1, l = 1, r = n;
while(l < r){
int m = (l + r) >> 1;
if(p <= m){
i = i * 2;
r = m;
}
else{
i = i * 2 + 1;
l = m + 1;
}
}
val[i] = c;
while(i > 1){
i >>= 1;
val[i] = max(val[i * 2], val[i * 2 + 1]);
}
}
int get(int c){
if(val[1] < c) return -1;
int i = 1, l = 1, r = n;
while(l < r){
int m = (l + r) >> 1;
if(val[i * 2 + 1] >= c){
i = i * 2 + 1;
l = m + 1;
}
else{
i = i * 2;
r = m;
}
}
return l;
}
};
struct fen{
vector<int> tree;
int n;
fen(int _n = 0){
n = _n;
tree.resize(n + 3, 0);
}
void upd(int p, int c){
while(p <= n){
tree[p] += c;
p += p & -p;
}
}
int get(int p){
int ans = 0;
while(p > 0){
ans += tree[p];
p -= p & -p;
}
return ans;
}
};
const int MAX = 2e5 + 10;
int N, Q;
pair<int, int> a[MAX], q[MAX];
void solve(){
cin >> N >> Q;
for(int i=1; i<=N; i++){
cin >> a[i].fi >> a[i].se;
}
for(int i=1; i<=Q; i++){
cin >> q[i].fi;
q[i].se = i;
}
sort(a + 1, a + N + 1, [&](const pair<int, int> &a, const pair<int, int> &b){return max(a.fi, a.se) > max(b.fi, b.se);});
sort(q + 1, q + Q + 1, greater<pair<int, int>>());
fen bit(Q);
seg it(Q);
for(int i=1; i<=N; i++){
it.upd(q[i].se, q[i].fi);
}
int j = 1;
ll ans = 0;
for(int i=1; i<=N; i++){
while(j <= Q && q[j].fi >= max(a[i].fi, a[i].se)){
bit.upd(q[j].se, 1);
it.upd(q[j].se, 0);
j++;
}
int p = it.get(min(a[i].fi, a[i].se));
if(p == -1){
int c = bit.get(Q);
if((c + (a[i].fi < a[i].se)) % 2 == 0){
ans += max(a[i].fi, a[i].se);
}
else{
ans += min(a[i].fi, a[i].se);
}
}
else{
int c = bit.get(Q) - bit.get(p);
if(c % 2 == 0){
ans += max(a[i].fi, a[i].se);
}
else{
ans += min(a[i].fi, a[i].se);
}
}
}
cout << ans << '\n';
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
// freopen("mmgraph.inp", "r", stdin);
// freopen("mmgraph.out", "w", stdout);
int t = 1;
// cin >> t;
while(t--){
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
