#include <bits/stdc++.h>
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
//#pragma GCC optimize("unroll-loops")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 2e5+20,mod = 1e9+7 ,inf = 1e9+10,maxm = (1 << 18)+10;
inline int mkay(int a,int b){
if (a+b >= mod) return a+b-mod;
if (a+b < 0) return a+b+mod;
return a+b;
}
inline int poww(int a,int k){
if (k < 0) return 0;
int z = 1;
while (k){
if (k&1) z = 1ll*z*a%mod;
a = 1ll*a*a%mod;
k >>= 1;
}
return z;
}
inline bool cmp(pll x,pll y){
return (x > y);
}
int fen[N],sp[N][20],k;
void upd(int l){
for(; l < k; l |= (l+1))
fen[l]++;
}
int que(int l,int r){
r--;
l--;
int ans = 0;
for (; r >= 0; r = (r&(r+1))-1 ){
ans += fen[r];
}
for (; l >= 0; l = (l&(l+1))-1){
ans -= fen[l];
}
return ans;
}
int main(){
ios :: sync_with_stdio(0); cin.tie(0);
int n;
ll ans = 0;
vector<pll> v1,v2,q;
cin >> n >> k;
rep(i,0,n){
int a,b;
cin >> a >> b;
if (a == b){
ans += b;
continue;
}
if (a > b) v1.pb({a,b});
else v2.pb({b,a});
}
sort(v1.begin(),v1.end(),cmp);
sort(v2.begin(),v2.end(),cmp);
rep(i,0,k){
int t;
cin >> t;
q.pb({t,i});
}
sort(q.begin(),q.end());
rep(i,0,k) sp[i][0] = q[i].Y;
rep(j,1,20){
rep(i,0,k){
sp[i][j] = sp[i][j-1];
if (i-(1 << j) >= 0)
sp[i][j] = max(sp[i][j],sp[i-(1 << j)][j-1]);
}
}
int po = k-1;
for (pll p : v1){
while (po >= 0 && q[po].X >= p.X){
upd(q[po].Y);
po--;
}
if (po < 0 || q[po].X < p.Y){
if ((k+1-po)&1) ans += p.Y;
else ans += p.X;
continue;
}
int ind = lower_bound(q.begin(),q.end(),make_pair(p.Y,0))-q.begin();
int g = 31-__builtin_clz(po-ind+1);
int mx = max(sp[po][g],sp[ind+(1 << g)-1][g]);
if (que(mx+1,k)&1) ans += p.Y;
else ans += p.X;
}
po = k-1;
memset(fen,0,sizeof fen);
for (pll p : v2){
while (po >= 0 && q[po].X >= p.X){
upd(q[po].Y);
po--;
}
if (po < 0 || (po >= 0 && q[po].X < p.Y)){
if ((k-po+1)&1) ans += p.X;
else ans += p.Y;
continue;
}
int ind = lower_bound(q.begin(),q.end(),make_pair(p.Y,0))-q.begin();
int g = 31-__builtin_clz(po-ind+1);
int mx = max(sp[po][g],sp[ind+(1 << g)-1][g]);
if (que(mx+1,k)&1) ans += p.Y;
else ans += p.X;
}
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
