#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int K=1<<20;
int n,k;
int a[N],b[N],c[2*N],t[N];
int side[N];
vector<int> vec[N];
long long ans;
struct segtree{
int t[K];
void update(int l,int r,int i,int x,int v){
if(x<l||r<x)return;
t[i]=max(t[i],v);
if(l==r)return;
int m=(l+r)/2;
update(l,m,i*2,x,v);
update(m+1,r,i*2+1,x,v);
}
void update(int x,int v){
update(1,2*n,1,x,v);
}
int query(int l,int r,int i,int x,int y){
if(y<l||r<x)return 0;
if(x<=l&&r<=y)return t[i];
int m=(l+r)/2;
return max(query(l,m,i*2,x,y),query(m+1,r,i*2+1,x,y));
}
int query(int x,int y){
return query(1,2*n,1,x,y);
}
}s;
struct fenwick{
int t[2*N];
void add(int i,int v){
while(i<2*N)t[i]+=v,i+=i&-i;
}
int read(int i){
int res=0;
while(i>0)res+=t[i],i-=i&-i;
return res;
}
}f;
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> k;
for(int i=1;i<=n;i++){
cin >> a[i] >> b[i];
c[i*2-1]=a[i];
c[i*2]=b[i];
}
sort(c+1,c+2*n+1);
for(int i=1;i<=n;i++){
a[i]=lower_bound(c+1,c+2*n+1,a[i])-c;
b[i]=lower_bound(c+1,c+2*n+1,b[i])-c;
}
for(int i=1;i<=k;i++){
cin >> t[i];
t[i]=upper_bound(c+1,c+2*n+1,t[i])-c-1;
s.update(t[i],i);
}
for(int i=1;i<=n;i++){
int pos;
if(a[i]<b[i]){
pos=s.query(a[i],b[i]-1);
side[i]=1;
}else{
pos=s.query(b[i],a[i]-1);
side[i]=0;
}
if(pos==0)side[i]=0;
vec[pos].emplace_back(i);
}
for(int i=k;i>=0;i--){
for(auto j:vec[i])ans+=c[(side[j]+f.read(2*n)-f.read(max(a[j],b[j])-1))%2==0?a[j]:b[j]];
if(t[i])f.add(t[i],1);
}
cout << ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
10588 KB |
Output is correct |
2 |
Correct |
2 ms |
10588 KB |
Output is correct |
3 |
Correct |
2 ms |
10588 KB |
Output is correct |
4 |
Correct |
2 ms |
10588 KB |
Output is correct |
5 |
Correct |
2 ms |
10588 KB |
Output is correct |
6 |
Correct |
2 ms |
10588 KB |
Output is correct |
7 |
Correct |
2 ms |
10588 KB |
Output is correct |
8 |
Correct |
3 ms |
10588 KB |
Output is correct |
9 |
Correct |
2 ms |
10588 KB |
Output is correct |
10 |
Correct |
2 ms |
10588 KB |
Output is correct |
11 |
Correct |
2 ms |
10588 KB |
Output is correct |
12 |
Correct |
2 ms |
10788 KB |
Output is correct |
13 |
Correct |
2 ms |
10588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
10588 KB |
Output is correct |
2 |
Correct |
2 ms |
10588 KB |
Output is correct |
3 |
Correct |
2 ms |
10588 KB |
Output is correct |
4 |
Correct |
2 ms |
10588 KB |
Output is correct |
5 |
Correct |
2 ms |
10588 KB |
Output is correct |
6 |
Correct |
2 ms |
10588 KB |
Output is correct |
7 |
Correct |
2 ms |
10588 KB |
Output is correct |
8 |
Correct |
3 ms |
10588 KB |
Output is correct |
9 |
Correct |
2 ms |
10588 KB |
Output is correct |
10 |
Correct |
2 ms |
10588 KB |
Output is correct |
11 |
Correct |
2 ms |
10588 KB |
Output is correct |
12 |
Correct |
2 ms |
10788 KB |
Output is correct |
13 |
Correct |
2 ms |
10588 KB |
Output is correct |
14 |
Correct |
12 ms |
11096 KB |
Output is correct |
15 |
Correct |
26 ms |
11348 KB |
Output is correct |
16 |
Correct |
32 ms |
11612 KB |
Output is correct |
17 |
Correct |
44 ms |
12252 KB |
Output is correct |
18 |
Correct |
43 ms |
12112 KB |
Output is correct |
19 |
Correct |
44 ms |
12260 KB |
Output is correct |
20 |
Correct |
42 ms |
12248 KB |
Output is correct |
21 |
Correct |
39 ms |
12304 KB |
Output is correct |
22 |
Correct |
32 ms |
12112 KB |
Output is correct |
23 |
Correct |
31 ms |
12124 KB |
Output is correct |
24 |
Correct |
31 ms |
12248 KB |
Output is correct |
25 |
Correct |
29 ms |
12132 KB |
Output is correct |
26 |
Correct |
29 ms |
11644 KB |
Output is correct |
27 |
Correct |
41 ms |
12252 KB |
Output is correct |
28 |
Correct |
31 ms |
11604 KB |
Output is correct |
29 |
Correct |
40 ms |
12252 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
10588 KB |
Output is correct |
2 |
Correct |
2 ms |
10588 KB |
Output is correct |
3 |
Correct |
2 ms |
10588 KB |
Output is correct |
4 |
Correct |
2 ms |
10588 KB |
Output is correct |
5 |
Correct |
2 ms |
10588 KB |
Output is correct |
6 |
Correct |
2 ms |
10588 KB |
Output is correct |
7 |
Correct |
2 ms |
10588 KB |
Output is correct |
8 |
Correct |
3 ms |
10588 KB |
Output is correct |
9 |
Correct |
2 ms |
10588 KB |
Output is correct |
10 |
Correct |
2 ms |
10588 KB |
Output is correct |
11 |
Correct |
2 ms |
10588 KB |
Output is correct |
12 |
Correct |
2 ms |
10788 KB |
Output is correct |
13 |
Correct |
2 ms |
10588 KB |
Output is correct |
14 |
Correct |
12 ms |
11096 KB |
Output is correct |
15 |
Correct |
26 ms |
11348 KB |
Output is correct |
16 |
Correct |
32 ms |
11612 KB |
Output is correct |
17 |
Correct |
44 ms |
12252 KB |
Output is correct |
18 |
Correct |
43 ms |
12112 KB |
Output is correct |
19 |
Correct |
44 ms |
12260 KB |
Output is correct |
20 |
Correct |
42 ms |
12248 KB |
Output is correct |
21 |
Correct |
39 ms |
12304 KB |
Output is correct |
22 |
Correct |
32 ms |
12112 KB |
Output is correct |
23 |
Correct |
31 ms |
12124 KB |
Output is correct |
24 |
Correct |
31 ms |
12248 KB |
Output is correct |
25 |
Correct |
29 ms |
12132 KB |
Output is correct |
26 |
Correct |
29 ms |
11644 KB |
Output is correct |
27 |
Correct |
41 ms |
12252 KB |
Output is correct |
28 |
Correct |
31 ms |
11604 KB |
Output is correct |
29 |
Correct |
40 ms |
12252 KB |
Output is correct |
30 |
Correct |
63 ms |
10964 KB |
Output is correct |
31 |
Correct |
101 ms |
12264 KB |
Output is correct |
32 |
Correct |
152 ms |
14424 KB |
Output is correct |
33 |
Correct |
240 ms |
16332 KB |
Output is correct |
34 |
Correct |
24 ms |
12624 KB |
Output is correct |
35 |
Correct |
254 ms |
22288 KB |
Output is correct |
36 |
Correct |
244 ms |
22248 KB |
Output is correct |
37 |
Correct |
246 ms |
22092 KB |
Output is correct |
38 |
Correct |
252 ms |
22316 KB |
Output is correct |
39 |
Correct |
249 ms |
22348 KB |
Output is correct |
40 |
Correct |
211 ms |
21836 KB |
Output is correct |
41 |
Correct |
244 ms |
22256 KB |
Output is correct |
42 |
Correct |
241 ms |
22100 KB |
Output is correct |
43 |
Correct |
124 ms |
19224 KB |
Output is correct |
44 |
Correct |
128 ms |
20064 KB |
Output is correct |
45 |
Correct |
125 ms |
20584 KB |
Output is correct |
46 |
Correct |
169 ms |
20428 KB |
Output is correct |
47 |
Correct |
165 ms |
20648 KB |
Output is correct |
48 |
Correct |
177 ms |
20564 KB |
Output is correct |
49 |
Correct |
167 ms |
20160 KB |
Output is correct |