#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
llo n,k;
llo aa[200001];
llo bb[200001];
llo pp[200001];
vector<llo> tree2[1];
vector<pair<llo,llo>> tree[800001];
llo build2(llo no1,llo no,llo l,llo r){
if(l==r){
tree2[no1][no]=tree[no1][l].b;
}
else{
llo mid=(l+r)/2;
build2(no1,no*2+1,l,mid);
build2(no1,no*2+2,mid+1,r);
tree2[no1][no]=max(tree2[no1][no*2+1],tree2[no1][no*2+2]);
/*if(no1==0){
cout<<tree2[no][no]<<","<<l<<","<<r<<endl;
}*/
}
}
llo query3(llo no1,llo no,llo l,llo r,llo aa,llo bb){
if(r<aa or l>bb){
return -1;
}
//cout<<l<<"..."<<r<<endl;
if(aa<=l and r<=bb){
return tree2[no1][no];
}
else{
llo mid=(l+r)/2;
return max(query3(no1,no*2+1,l,mid,aa,bb),query3(no1,no*2+2,mid+1,r,aa,bb));
}
}
llo build(llo no,llo l,llo r){
if(no==0){
for(llo i=0;i<(r-l+1)*4;i++){
tree2[no].pb(0);
}
}
if(l==r){
tree[no].pb({pp[l],l});
}
else{
llo mid=(l+r)/2;
build(no*2+1,l,mid);
build(no*2+2,mid+1,r);
llo ind=0;
llo ind2=0;
while(ind<tree[no*2+1].size() and ind2<tree[no*2+2].size()){
if(tree[no*2+1][ind].a<tree[no*2+2][ind2].a){
tree[no].pb(tree[no*2+1][ind]);
ind+=1;
}
else{
tree[no].pb(tree[no*2+2][ind2]);
ind2+=1;
}
}
while(ind<tree[no*2+1].size()){
tree[no].pb(tree[no*2+1][ind]);
ind+=1;
}
while(ind2<tree[no*2+2].size()){
tree[no].pb(tree[no*2+2][ind2]);
ind2+=1;
}
}
if(no==0){
build2(no,0,0,r-l);
}
}
llo val1;
llo val2;
llo val3;
llo query(llo no,llo l,llo r,llo aa,llo bb){
if(tree[no].back().a<val1){
return -1;
}
if(tree[no][0].a>=val2){
return -1;
}
// cout<<l<<"::"<<r<<endl;
llo low=0;
llo high=r-l;
if(high>=tree[no].size()){
return -1;
}
while(low<high-1){
llo mid=(l+r)/2;
if(tree[no][mid].a>=val1){
high=mid;
}
else{
low=mid;
}
}
llo ind=high;
if(tree[no][low].a>=val1){
ind=min(ind,low);
}
low=0;
high=r-l;
while(low<high-1){
llo mid=(l+r)/2;
if(tree[no][mid].a<val2){
low=mid;
}
else{
high=mid;
}
}
llo ind2=low;
if(tree[no][high].a<val2){
ind2=max(ind2,high);
}
// cout<<ind<<",,,,,"<<ind2<<endl;
if(ind>ind2){
return -1;
}
return query3(no,0,0,r-l,ind,ind2);
}
llo query2(llo no,llo l,llo r,llo aa,llo bb){
if(r<aa or bb<l){
return 0;
}
if(aa<=l and r<=bb){
if(tree[no].back().a<val3){
return 0;
}
llo low=0;
llo high=r-l;
while(low<high-1){
llo mid=(l+r)/2;
if(tree[no][mid].a>=val3){
high=mid;
}
else{
low=mid;
}
}
llo ind=high;
if(tree[no][low].a>=val3){
ind=min(ind,low);
}
return (llo)(tree[no].size())-ind;
}
else{
llo mid=(l+r)/2;
return query2(no*2+1,l,mid,aa,bb)+query2(no*2+2,mid+1,r,aa,bb);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>k;
for(llo i=0;i<n;i++){
cin>>aa[i];
cin>>bb[i];
}
for(llo i=0;i<k;i++){
cin>>pp[i];
}
build(0,0,k-1);
llo ans=0;
for(llo i=0;i<n;i++){
val1=min(aa[i],bb[i]);
val2=max(aa[i],bb[i]);
// cout<<val1<<"///"<<val2<<endl;
llo indd=query(0,0,k-1,0,k-1);
continue;
indd+=1;
// cout<<i<<","<<indd-1<<endl;
if(indd>=k){
if(aa[i]<bb[i]){
ans+=bb[i];
}
else if(bb[i]<aa[i]){
ans+=aa[i];
}
continue;
}
val3=max(val1,val2);
llo co=query2(0,0,k-1,indd,k-1);
//cout<<co<<endl;
llo st;
if(indd==0){
st=0;
}
else{
if(aa[i]<bb[i]){
st=1;
}
else{
st=0;
}
}
st+=co;
st%=2;
if(st==1){
ans+=bb[i];
}
else{
ans+=aa[i];
}
}
cout<<ans<<endl;
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'llo build2(llo, llo, llo, llo)':
fortune_telling2.cpp:29:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
fortune_telling2.cpp: In function 'llo build(llo, llo, llo)':
fortune_telling2.cpp:60:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind<tree[no*2+1].size() and ind2<tree[no*2+2].size()){
~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:60:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind<tree[no*2+1].size() and ind2<tree[no*2+2].size()){
~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:70:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind<tree[no*2+1].size()){
~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:74:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind2<tree[no*2+2].size()){
~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:82:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
fortune_telling2.cpp: In function 'llo query(llo, llo, llo, llo, llo)':
fortune_telling2.cpp:97:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(high>=tree[no].size()){
~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3093 ms |
19456 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3093 ms |
19456 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3093 ms |
19456 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
