#include <bits/stdc++.h>
using namespace std;
const int nx=2e5+5;
int n, k, a[nx], b[nx], t[nx], l[nx], sw[nx], cnt[nx];
long long res;
vector<int> v, d[nx];
struct segtree
{
int d[4*nx];
void update(int l, int r, int i, int idx, int vl)
{
if (idx<l||r<idx) return;
if (l==r) return void(d[i]=max(d[i], vl));
int md=(l+r)/2;
update(l, md, 2*i, idx, vl);
update(md+1, r, 2*i+1, idx, vl);
d[i]=max(d[2*i], d[2*i+1]);
}
int query(int l, int r, int i, int ql, int qr)
{
if (ql<=l&&r<=qr) return d[i];
if (qr<l||r<ql) return 0;
int md=(l+r)/2;
return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
}
} s;
struct segtreesum
{
int d[4*nx];
void update(int l, int r, int i, int idx, int vl)
{
if (idx<l||r<idx) return;
if (l==r) return void(d[i]+=vl);
int md=(l+r)/2;
update(l, md, 2*i, idx, vl);
update(md+1, r, 2*i+1, idx, vl);
d[i]=d[2*i]+d[2*i+1];
}
int query(int l, int r, int i, int ql, int qr)
{
if (ql<=l&&r<=qr) return d[i];
if (qr<l||r<ql) return 0;
int md=(l+r)/2;
return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
}
} ss;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>k;
for (int i=1; i<=n; i++) cin>>a[i]>>b[i];
for (int i=1; i<=n; i++) if (a[i]>b[i]) swap(a[i], b[i]), sw[i]=1;
for (int i=1; i<=k; i++) cin>>t[i], v.push_back(t[i]);
sort(v.begin(), v.end());
for (int i=1; i<=k; i++) s.update(1, k, 1, lower_bound(v.begin(), v.end(), t[i])-v.begin()+1, i);
for (int i=1; i<=n; i++)
{
int ql=lower_bound(v.begin(), v.end(), a[i])-v.begin()+1;
int qr=upper_bound(v.begin(), v.end(), b[i]-1)-v.begin();
if (ql>k||qr<1||qr<ql) continue;
l[i]=s.query(1, k, 1, ql, qr);
}
for (int i=1; i<=n; i++) d[l[i]].push_back(i);
for (int i=k; i>=0; i--)
{
for (auto x:d[i])
{
int qr=lower_bound(v.begin(), v.end(), b[x])-v.begin()+1, tmp;
if (qr>k) tmp=0;
else tmp=ss.query(1, k, 1, qr, k);
if (i!=0&&tmp%2==0) res+=b[x];
else if (i!=0) res+=a[x];
else if (tmp%2==0&&sw[x]==0) res+=a[x];
else res+=b[x];
//cout<<x<<' '<<tmp<<' '<<qr<<' '<<res<<'\n';
}
if (i!=0) ss.update(1, k, 1, lower_bound(v.begin(), v.end(), t[i])-v.begin()+1, 1);
}
cout<<res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
