#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mn=2e5+10;
int a[mn],b[mn],si[mn],v[mn];
vector<int>seg[mn*4];
#define mid ((l+r)>>1)
void init(int x,int l,int r){
for(int i=l;i<=r;i++)seg[x].push_back(v[i]);
sort(seg[x].begin(),seg[x].end());
if(l!=r){
init(x*2,l,mid);
init(x*2+1,mid+1,r);
}
}
int numg(vector<int>&v,int x){
return v.size()-(lower_bound(v.begin(),v.end(),x)-v.begin());
}
int query1(int x,int l,int r,int a,int b){
if(l==r){
assert(seg[x].size()==1);
if(a<=seg[x][0]&&seg[x][0]<b)return l;
else return l-1;
}
else{
if(numg(seg[x*2+1],a)-numg(seg[x*2+1],b))return query1(x*2+1,mid+1,r,a,b);
else return query1(x*2,l,mid,a,b);
}
}
int num(int x,int l,int r,int a,int b,int c){
if(l==a&&r==b)return numg(seg[x],c);
if(b<=mid)return num(x*2,l,mid,a,b,c);
else if(a>mid)return num(x*2+1,mid+1,r,a,b,c);
else return num(x*2,l,mid,a,mid,c)+num(x*2+1,mid+1,r,mid+1,b,c);
}
int main(){
cin.tie(0);
cin.sync_with_stdio(0);
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>a[i]>>b[i];
if(a[i]>b[i]){
swap(a[i],b[i]);
si[i]=1;
}
}
for(int i=1;i<=k;i++){
cin>>v[i];
}
init(1,1,k);
ll ans=0;
for(int i=0;i<n;i++){
int t=query1(1,1,k,a[i],b[i]);
if(t)si[i]=1;
if(t<k)si[i]+=num(1,1,k,t+1,k,a[i]);
if(si[i]&1)ans+=b[i];
else ans+=a[i];
}
printf("%lld",ans);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
19200 KB |
Output is correct |
2 |
Correct |
16 ms |
19200 KB |
Output is correct |
3 |
Correct |
17 ms |
19328 KB |
Output is correct |
4 |
Correct |
19 ms |
19328 KB |
Output is correct |
5 |
Correct |
17 ms |
19328 KB |
Output is correct |
6 |
Correct |
17 ms |
19328 KB |
Output is correct |
7 |
Correct |
18 ms |
19328 KB |
Output is correct |
8 |
Correct |
16 ms |
19328 KB |
Output is correct |
9 |
Correct |
17 ms |
19328 KB |
Output is correct |
10 |
Correct |
16 ms |
19328 KB |
Output is correct |
11 |
Correct |
17 ms |
19232 KB |
Output is correct |
12 |
Correct |
17 ms |
19328 KB |
Output is correct |
13 |
Correct |
17 ms |
19328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
19200 KB |
Output is correct |
2 |
Correct |
16 ms |
19200 KB |
Output is correct |
3 |
Correct |
17 ms |
19328 KB |
Output is correct |
4 |
Correct |
19 ms |
19328 KB |
Output is correct |
5 |
Correct |
17 ms |
19328 KB |
Output is correct |
6 |
Correct |
17 ms |
19328 KB |
Output is correct |
7 |
Correct |
18 ms |
19328 KB |
Output is correct |
8 |
Correct |
16 ms |
19328 KB |
Output is correct |
9 |
Correct |
17 ms |
19328 KB |
Output is correct |
10 |
Correct |
16 ms |
19328 KB |
Output is correct |
11 |
Correct |
17 ms |
19232 KB |
Output is correct |
12 |
Correct |
17 ms |
19328 KB |
Output is correct |
13 |
Correct |
17 ms |
19328 KB |
Output is correct |
14 |
Correct |
42 ms |
20864 KB |
Output is correct |
15 |
Correct |
69 ms |
22816 KB |
Output is correct |
16 |
Correct |
100 ms |
23928 KB |
Output is correct |
17 |
Correct |
134 ms |
26488 KB |
Output is correct |
18 |
Correct |
134 ms |
26492 KB |
Output is correct |
19 |
Correct |
134 ms |
26488 KB |
Output is correct |
20 |
Correct |
139 ms |
26492 KB |
Output is correct |
21 |
Correct |
118 ms |
26488 KB |
Output is correct |
22 |
Correct |
91 ms |
25976 KB |
Output is correct |
23 |
Correct |
92 ms |
26104 KB |
Output is correct |
24 |
Correct |
93 ms |
25976 KB |
Output is correct |
25 |
Correct |
89 ms |
26104 KB |
Output is correct |
26 |
Correct |
110 ms |
26360 KB |
Output is correct |
27 |
Correct |
142 ms |
26488 KB |
Output is correct |
28 |
Correct |
110 ms |
26616 KB |
Output is correct |
29 |
Correct |
155 ms |
26488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
19200 KB |
Output is correct |
2 |
Correct |
16 ms |
19200 KB |
Output is correct |
3 |
Correct |
17 ms |
19328 KB |
Output is correct |
4 |
Correct |
19 ms |
19328 KB |
Output is correct |
5 |
Correct |
17 ms |
19328 KB |
Output is correct |
6 |
Correct |
17 ms |
19328 KB |
Output is correct |
7 |
Correct |
18 ms |
19328 KB |
Output is correct |
8 |
Correct |
16 ms |
19328 KB |
Output is correct |
9 |
Correct |
17 ms |
19328 KB |
Output is correct |
10 |
Correct |
16 ms |
19328 KB |
Output is correct |
11 |
Correct |
17 ms |
19232 KB |
Output is correct |
12 |
Correct |
17 ms |
19328 KB |
Output is correct |
13 |
Correct |
17 ms |
19328 KB |
Output is correct |
14 |
Correct |
42 ms |
20864 KB |
Output is correct |
15 |
Correct |
69 ms |
22816 KB |
Output is correct |
16 |
Correct |
100 ms |
23928 KB |
Output is correct |
17 |
Correct |
134 ms |
26488 KB |
Output is correct |
18 |
Correct |
134 ms |
26492 KB |
Output is correct |
19 |
Correct |
134 ms |
26488 KB |
Output is correct |
20 |
Correct |
139 ms |
26492 KB |
Output is correct |
21 |
Correct |
118 ms |
26488 KB |
Output is correct |
22 |
Correct |
91 ms |
25976 KB |
Output is correct |
23 |
Correct |
92 ms |
26104 KB |
Output is correct |
24 |
Correct |
93 ms |
25976 KB |
Output is correct |
25 |
Correct |
89 ms |
26104 KB |
Output is correct |
26 |
Correct |
110 ms |
26360 KB |
Output is correct |
27 |
Correct |
142 ms |
26488 KB |
Output is correct |
28 |
Correct |
110 ms |
26616 KB |
Output is correct |
29 |
Correct |
155 ms |
26488 KB |
Output is correct |
30 |
Correct |
323 ms |
49388 KB |
Output is correct |
31 |
Correct |
424 ms |
50544 KB |
Output is correct |
32 |
Correct |
542 ms |
52208 KB |
Output is correct |
33 |
Correct |
789 ms |
55328 KB |
Output is correct |
34 |
Correct |
293 ms |
48984 KB |
Output is correct |
35 |
Correct |
798 ms |
55356 KB |
Output is correct |
36 |
Correct |
800 ms |
55152 KB |
Output is correct |
37 |
Correct |
805 ms |
55124 KB |
Output is correct |
38 |
Correct |
774 ms |
55216 KB |
Output is correct |
39 |
Correct |
814 ms |
55280 KB |
Output is correct |
40 |
Correct |
657 ms |
55024 KB |
Output is correct |
41 |
Correct |
784 ms |
55164 KB |
Output is correct |
42 |
Correct |
799 ms |
55156 KB |
Output is correct |
43 |
Correct |
450 ms |
54508 KB |
Output is correct |
44 |
Correct |
445 ms |
54508 KB |
Output is correct |
45 |
Correct |
445 ms |
54384 KB |
Output is correct |
46 |
Correct |
485 ms |
53232 KB |
Output is correct |
47 |
Correct |
516 ms |
53104 KB |
Output is correct |
48 |
Correct |
699 ms |
55148 KB |
Output is correct |
49 |
Correct |
621 ms |
55152 KB |
Output is correct |