#include<bits/stdc++.h>
using namespace std;
#define N 200005
class node{
public:
node *l,*r;
int cnt;
node(int cnt):l(NULL),r(NULL),cnt(cnt){}
node(node *l,node *r):l(l),r(r),cnt(0){
if(l)cnt+=l->cnt;
if(r)cnt+=r->cnt;
}
};
using pnode = node*;
pnode root[N];
pnode cre(int l,int r){
if(l==r)return new node(0);
int mid=(l+r)/2;
return new node(cre(l,mid),cre(mid+1,r));
}
pnode update(pnode x,int l,int r,int p){
if(l==r)return new node(x->cnt+1);
int mid=(l+r)/2;
if(p<=mid)return new node(update(x->l,l,mid,p),x->r);
else new node(x->l,update(x->r,mid+1,r,p));
}
int sol(pnode x,int l,int r,int ll,int rr){
if(l>rr||ll>r||ll>rr)return 0;
if(ll<=l&&r<=rr)return x->cnt;
int mid=(l+r)/2;
return sol(x->l,l,mid,ll,rr)+sol(x->r,mid+1,r,ll,rr);
}
int a[N],b[N],t[N],sz;
long long ans;
vector<int> v;
map<int,int> mp;
int main(){
int n,m,i,mi,ma,pmi,pma,pos,l,r,mid,cnt;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d %d",&a[i],&b[i]);
}
for(i=1;i<=m;i++)scanf("%d",&t[i]),mp[t[i]],v.push_back(t[i]);
v.push_back(-1);
sort(v.begin(),v.end());
v.resize(unique(v.begin(),v.end())-v.begin());
for(auto &[x,y]:mp)y=++sz;
root[0]=cre(1,sz);
for(i=1;i<=m;i++){
root[i]=update(root[i-1],1,sz,mp[t[i]]);
}
for(i=1;i<=n;i++){
//search for last t that mi <= t < ma
auto [mi,ma]=minmax(a[i],b[i]);
pmi=lower_bound(v.begin(),v.end(),mi)-v.begin();
pma=lower_bound(v.begin(),v.end(),ma)-v.begin();
pos=0;
l=1,r=sz;
while(l<=r){
mid=(l+r)/2;
cnt=sol(root[m],1,sz,pmi,pma-1)-sol(root[mid-1],1,sz,pmi,pma-1);
if(cnt)pos=mid,l=mid+1;
else r=mid-1;
}
if(pos){
cnt=sol(root[m],1,sz,pma,sz)-sol(root[pos-1],1,sz,pma,sz);
ans+=(cnt%2)?mi:ma;
}
else{
cnt=sol(root[m],1,sz,pma,sz);
ans+=(cnt%2)?b[i]:a[i];
}
}
printf("%lld",ans);
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:45:15: warning: unused variable 'mi' [-Wunused-variable]
45 | int n,m,i,mi,ma,pmi,pma,pos,l,r,mid,cnt;
| ^~
fortune_telling2.cpp:45:18: warning: unused variable 'ma' [-Wunused-variable]
45 | int n,m,i,mi,ma,pmi,pma,pos,l,r,mid,cnt;
| ^~
fortune_telling2.cpp: In function 'node* update(pnode, int, int, int)':
fortune_telling2.cpp:29:46: warning: control reaches end of non-void function [-Wreturn-type]
29 | else new node(x->l,update(x->r,mid+1,r,p));
| ^
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | scanf("%d %d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~
fortune_telling2.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | scanf("%d %d",&a[i],&b[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:50:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | for(i=1;i<=m;i++)scanf("%d",&t[i]),mp[t[i]],v.push_back(t[i]);
| ~~~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
