#include<stdio.h>
#include<vector>
#include<algorithm>
void set2(int x, int v);
int getsum2(int f, int r);
void set1(int x, int v);
int getmax1(int f, int r);
int max(int a, int b){return a>b?a:b;}
int min(int a, int b){return a<b?a:b;}
std::vector<int> X;
int a[200001];
int b[200001];
int q[200001];
int base;
struct dat
{
int i, loc, o;
bool operator<(const dat &A) const{return loc<A.loc;}
} D[200001];
int main()
{
int n, k;
int i, j;
scanf("%d%d", &n, &k);
for(i=1; i<=n; i++)
{
scanf("%d%d", a+i, b+i);
if(a[i] > b[i]){int t = a[i]; a[i] = b[i]; b[i] = t; D[i].o = 1;}
X.push_back(a[i]);
X.push_back(b[i]);
}
std::sort(X.begin(), X.end());
X.erase(std::unique(X.begin(), X.end()), X.end());
for(base=1; base<=X.size()+1; base*=2);
for(i=1; i<=n; i++)
{
a[i] = std::lower_bound(X.begin(), X.end(), a[i]) - X.begin() + 1;
b[i] = std::lower_bound(X.begin(), X.end(), b[i]) - X.begin() + 1;
}
for(i=1; i<=k; i++)
{
scanf("%d", q+i);
q[i] = std::lower_bound(X.begin(), X.end(), q[i]) - X.begin() + 1;
set1(q[i], i);
set2(q[i], 1);
}
for(i=1; i<=n; i++)
{
int l = getmax1(a[i], b[i]-1);
D[i].i = i;
D[i].loc = l;
if(l!=0) D[i].o = 1;
}
std::sort(D+1, D+1+n);
j=1;
long long sum = 0;
for(i=1; i<=n; i++)
{
for(; j<=D[i].loc; j++)set2(q[j], -1);
if((D[i].o + getsum2(b[D[i].i], X.size()))&1) sum += X[b[D[i].i]-1];
else sum += X[a[D[i].i]-1];
}
printf("%lld", sum);
return 0;
}
int IT1[550000*2];
void set1(int x, int v){for(IT1[x+=base] = v; x/=2;)IT1[x]=max(IT1[2*x], IT1[2*x+1]);}
int getmax1(int f, int r)
{
f+=base; r+=base;
int re = 0;
while(f<r)
{
if(f%2==1) re = max(re, IT1[f++]);
if(r%2==0) re = max(re, IT1[r--]);
f/=2; r/=2;
}
if(f==r) re = max(re, IT1[f]);
return re;
}
int IT2[550000*2];
void set2(int x, int v){for(IT2[x+=base] += v; x/=2;)IT2[x]=IT2[2*x]+IT2[2*x+1];}
int getsum2(int f, int r)
{
f+=base; r+=base;
int re = 0;
while(f<r)
{
if(f%2==1) re += IT2[f++];
if(r%2==0) re += IT2[r--];
f/=2; r/=2;
}
if(f==r) re += IT2[f];
return re;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
14500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
14632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
112 ms |
14632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
