#include<bits/stdc++.h>
#define ll long long
#define sz(x) (signed)x.size()
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,l,r) for(int i=r;i>=l;i--)
#define F "CHOTMH"
#define fio freopen(F".inp","r",stdin);freopen(F".out","w",stdout);
using namespace std;
int n,k;
const int N=2e5+3;
struct BIT {
int pf[N];
void upd(int u,int val) {
while(u<=k) {
pf[u]=pf[u]+val;
u+=u&(-u);
}
}
int query(int u) {
int ans=0;
while(u>0) {
ans+=pf[u];
u-=u&(-u);
}
return ans;
}
};
struct BITT {
int pf[N];
void upd(int u,int val) {
while(u<=k) {
pf[u]=min(pf[u],val);
u+=u&(-u);
}
}
int query(int u) {
int ans=2e9;
while(u>0) {
ans=min(pf[u],ans);
u-=u&(-u);
}
return ans;
}
};
BIT bit;
BITT sus;
vector<int> in[N],sigma[N],sigma1[N],big;
pair<int,int> a[N];
bool huhu[N];
int q[N],pf[N],pp[N];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
ll ans=0;
For(i,1,n) {
cin >> a[i].ff >> a[i].ss;
big.pb(a[i].ff);
big.pb(a[i].ss);
}
For(i,1,k) {
bit.pf[i]=0;
sus.pf[i]=2e9;
cin >> q[i];
big.pb(q[i]);
pf[i]=max(pf[i-1],q[i]);
}
sort(big.begin(),big.end());
big.resize(unique(big.begin(),big.end())-big.begin());
For(i,1,k) {
int ind=lower_bound(big.begin(),big.end(),q[i])-big.begin();
in[ind+1].pb(i);
}
For(i,1,n) {
int ind=lower_bound(big.begin(),big.end(),a[i].ff)-big.begin();
int ind1=lower_bound(big.begin(),big.end(),a[i].ss)-big.begin();
if (a[i].ff!=a[i].ss) {
sigma[min(ind,ind1)+1].pb(i);
sigma1[max(ind,ind1)+1].pb(i);
}
else ans+=a[i].ff,huhu[i]=1;
}
ForD(i,1,sz(big)) {
for(auto el: in[i]) sus.upd(k-el+1,q[el]);
for(auto el: sigma[i]) {
int l=(a[el].ff<a[el].ss?(lower_bound(pf+1,pf+1+k,a[el].ff)-pf)+1:1),r=k;
int cc=l;
if (l>k) {
ans+=a[el].ss;
huhu[el]=1;
}
if (a[el].ff<a[el].ss) swap(a[el].ff,a[el].ss);
while(l<r) {
int mid=l+(r-l+1)/2;
if (sus.query(k-mid+1)<a[el].ff) l=mid;
else r=mid-1;
}
if (sus.query(k-l+1)<a[el].ff) pp[el]=l;
else pp[el]=cc;
}
}
ForD(i,1,sz(big)) {
for(auto el: in[i]) bit.upd(el,1);
for(auto el: sigma1[i]) {
if (huhu[el]) continue;
int tm=bit.query(k)-bit.query(pp[el]);
if (tm%2) ans+=a[el].ss;
else ans+=a[el].ff;
}
}
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
18768 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
18768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
18768 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
18768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
18768 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
18768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
