#include <bits/stdc++.h>
#define Size(x) ((int)(x).size())
#define endl '\n'
using namespace std;
template<typename T> using vc=vector<T>;
template<typename T> using vc1=vc<T>;
template<typename T> using vc2=vc<vc1<T>>;
template<typename T> using vc3=vc<vc2<T>>;
template<typename T> using vc4=vc<vc3<T>>;
template<typename T> using cr=const T&;
using pii=pair<int,int>;
using lli=long long int;
using pli=pair<lli,int>;
template<typename X,typename Y>
bool minimize(X&x,cr<Y>y){
return (y<x?x=y,true:false);
}
template<typename X,typename Y>
bool maximize(X&x,cr<Y>y){
return (y>x?x=y,true:false);
}
const int maxN=2e5;
const int maxM=2e5;
const int inf=0x3f3f3f3f;
const lli INF=0x3f3f3f3f3f3f3f3f;
struct Interval_Tree_Sum{
vc<int> Node;
int N;
Interval_Tree_Sum(int __N){
N=__N;
Node.resize(4*N+3,0);
return ;
}
void Upd(int i,int l,int r,int p,int v){
if(p<l||r<p)
return;
if(l==r){
Node[i]=v;
return ;
}
int m=(l+r)>>1;
if(p<=m)
Upd(i<<1,l,m,p,v);
else
Upd(i<<1|1,m+1,r,p,v);
Node[i]=Node[i<<1]+Node[i<<1|1];
return ;
}
void Upd(int p,int v){
Upd(1,1,N,p,v);
}
int Get(int i,int l,int r,int u,int v){
if(v<l||r<u)
return 0;
if(u<=l&&r<=v)
return Node[i];
int m=(l+r)>>1;
return Get(i<<1,l,m,u,v)+Get(i<<1|1,m+1,r,u,v);
}
int Get(int u,int v){
return Get(1,1,N,u,v);
}
};
struct Interval_Tree_Max{
vc<int> Node;
int N;
Interval_Tree_Max(int __N){
N=__N;
Node.resize(4*N+3);
}
void Build(int i,int l,int r,const pii *a){
if(l==r){
Node[i]=a[l].second;
return ;
}
int m=(l+r)>>1;
Build(i<<1,l,m,a);Build(i<<1|1,m+1,r,a);
Node[i]=max(Node[i<<1],Node[i<<1|1]);
return ;
}
void Build(const pii*a){
Build(1,1,N,a);
return ;
}
int Get(int i,int l,int r,int u,int v){
if(v<l||r<u||u>v)
return -1;
if(u<=l&&r<=v)
return Node[i];
int m=(l+r)>>1;
return max(Get(i<<1,l,m,u,v),Get(i<<1|1,m+1,r,u,v));
}
int Get(int u,int v){
return Get(1,1,N,u,v);
}
};
int N,K;
pii a[maxN+3];
pii t[maxN+3];
int main(){
//ios_base::sync_with_stdio(false);cin.tie(nullptr);
//freopen("t.inp","r",stdin);freopen("t.out","w",stdout);
scanf("%d%d",&N,&K);
for(int i=1;i<=N;i++)
scanf("%d%d",&a[i].first,&a[i].second);
sort(a+1,a+N+1,[]
(cr<pii>x,cr<pii>y){
return max(x.first,x.second)>max(y.first,y.second);
});
for(int i=1;i<=K;i++){
scanf("%d",&t[i].first);
t[i].second=i;
}
sort(t+1,t+K+1,[]
(cr<pii>x,cr<pii>y){
return x.first<y.first;
});
Interval_Tree_Sum ITS(N);
Interval_Tree_Max ITM(N);
ITM.Build(t);
lli res=0;
int pos=K;
for(int i=1;i<=N;i++){
while(pos&&t[pos].first>=max(a[i].first,a[i].second)){
ITS.Upd(t[pos].second,1);
pos--;
}
int l=lower_bound(t+1,t+K+1,pii(min(a[i].first,a[i].second),-1))-t;
int r=lower_bound(t+1,t+K+1,pii(max(a[i].first,a[i].second),-1))-t-1;
if(l<=r){
int maxpos=ITM.Get(l,r);
int d=ITS.Get(maxpos+1,N);
if(d&1)
res+=min(a[i].first,a[i].second);
else
res+=max(a[i].first,a[i].second);
//cout<<maxpos<<' '<<d<<'\n';
}
else{
int d=ITS.Get(1,N);
if(d&1)
res+=a[i].second;
else
res+=a[i].first;
//cout<<d<<'\n';
}
//cout<<a[i].first<<' '<<a[i].second<<' '<<res<<' '<<pos<<'\n';
}
cout<<res;
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:113:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
113 | scanf("%d%d",&N,&K);
| ~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
115 | scanf("%d%d",&a[i].first,&a[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:121:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
121 | scanf("%d",&t[i].first);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
