#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<utility>
#include<vector>
#include<stack>
#include<queue>
#include<cstring>
#include<set>
#include<map>
#define endl "\n"
#define all(v) v.begin(),v.end()
#define st first
#define nd second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long lo;
const int mod=1000000007,N=500005;
lo a,b,c,d,e,f,g=1,h[N],q;
vector<lo>tree[2*N];
pair<lo,lo> arr[N],degis[N];
string s;
vector<lo>v;
//----------------------------------------segment tree start
void build(lo n,lo l,lo r){
if(l==r){
tree[n].pb(degis[n].nd);
return;
}
build(2*n,l,(l+r)/2);
build(2*n+1,(l+r)/2+1,r);
lo x=0,y=0;
for(lo i=0;i<l+r-1;i++){
if(x==tree[2*n].size())tree[n].pb(tree[2*n+1][y++]);
else if(y==tree[2*n+1].size())tree[n].pb(tree[2*n][x++]);
else if(tree[2*n][x]<tree[2*n+1][y])tree[n].pb(tree[2*n][x++]);
else tree[n].pb(tree[2*n+1][y++]);
}
}
lo query(lo n,lo l,lo r,lo x,lo y,lo z){
if(x<=l and r<=y){
return (tree[n].end()-upper_bound(all(tree[n]),z));
}
if(r<x or y<l){
return 0;
}
return query(2*n,l,(l+r)/2,x,y,z)+
query(2*n+1,(l+r)/2+1,r,x,y,z);
}
lo query2(lo n,lo l,lo r,lo x,lo y){
if(x<=l and r<=y){
return tree[n][tree[n].size()-1];
}
if(r<x or y<l){
return 0;
}
return max(query2(2*n,l,(l+r)/2,x,y),query2(2*n+1,(l+r)/2+1,r,x,y));
}
//----------------------------------------segment tree end
lo bs(lo x){
lo l=1,r=b+1;
while(l<r){
lo mid=(l+r)/2;
if(degis[mid].st<x) l=mid+1;
else r=mid;
}
return r;
}
void solve(){
cin >> a >> b;
for(lo i=1;i<=a;i++){
cin >> arr[i].st >> arr[i].nd;
}
for(lo i=1;i<=b;i++){
cin >> degis[i].st;
degis[i].nd=i;
}
build(1,1,b);
sort(degis+1,degis+b+1);
lo sum=0;
for(lo i=1;i<=a;i++){
lo x=bs(arr[i].st),y=bs(arr[i].nd);
if(x<y){
lo hh=query(1,1,b,y,b,query2(1,1,b,x,y-1));
sum+=(hh%2?arr[i].st:arr[i].nd);
}
if(y<x){
lo hh=query(1,1,b,x,b,query2(1,1,b,y,x-1));
sum+=(hh%2?arr[i].nd:arr[i].st);
}
if(x==y){
sum+=((b-y+1)%2?arr[i].nd:arr[i].st);
}
}
cout << sum << endl;
}
int main(){
#ifdef local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
// cin >> g;
while(g--)solve();
}
Compilation message
fortune_telling2.cpp: In function 'void build(lo, lo, lo)':
fortune_telling2.cpp:38:7: warning: comparison of integer expressions of different signedness: 'lo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | if(x==tree[2*n].size())tree[n].pb(tree[2*n+1][y++]);
| ~^~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:39:12: warning: comparison of integer expressions of different signedness: 'lo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | else if(y==tree[2*n+1].size())tree[n].pb(tree[2*n][x++]);
| ~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
33900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
33900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
33900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
