#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t[N],tree_[N],tree[4*N],a[N],b[N],n,m;
vector<pair<int,int> > q,V;
set<pair<int,int> > s;
void update(int ind){
for(ind;ind>=1;ind-=ind&(-ind)){
tree_[ind]++;
}
}
int getans(int ind){
int pas=0;
for(ind;ind<=m;ind++){
pas+=tree_[ind];
}
return pas;
}
void update(int u,int ind,int l,int r,int val){
if(l>ind || r<ind) return;
if(l==r) {
tree[u]=val;
return;
}
int mid=(l+r)/2;
update(2*u,ind,l,mid,val);
update(2*u+1,ind,mid+1,r,val);
tree[u]=max(tree[2*u],tree[2*u+1]);
}
int getans(int u,int start,int end,int l,int r){
if(l>end || r<start) return 0;
if(start<=l && r<=end) return tree[u];
int mid=(l+r)/2;
return max(getans(2*u,start,end,l,mid),getans(2*u+1,start,end,mid+1,r));
}
main(){
// t=1;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i]; cin>>b[i];V.push_back({max(b[i],a[i]),i});
// v.push_back(a[i]);
}
for(int i=1;i<=m;i++){
cin>>t[i];
// v.push_back(t[i]);
q.push_back({t[i],i});
}
/*
sort(v.begin(),v.end());
int idx = 0;
for(int i=0;i<v.size();i++){
if(!i || v[i]!=v[i-1]) idx++;
ind[v[i]] = idx;
}*/
sort(V.rbegin(),V.rend());
sort(q.rbegin(),q.rend());
for(int i=0;i<q.size();i++){
s.insert({q[i].f,i});
update(1,i+1,1,m,q[i].s);
}
int l = -1,ans=0;
for(int i=0;i<V.size();i++){
while(l+1<q.size() && q[l+1].f>=V[i].f) l++,update(q[l].s);
int lst = 0;
if(s.upper_bound({min(a[V[i].s],b[V[i].s]),-1})!=s.end()){
lst =getans(1,l+1,(*s.upper_bound({min(a[V[i].s],b[V[i].s]),-1})).s,1,m);
if(a[V[i].s] < b[V[i].s]) swap(a[V[i].s],b[V[i].s]);
}
if(getans(lst)%2) ans+=b[V[i].s];else ans += a[V[i].s];
}
cout<<ans;
}
Compilation message
fortune_telling2.cpp: In function 'void update(long long int)':
fortune_telling2.cpp:11:6: warning: statement has no effect [-Wunused-value]
11 | for(ind;ind>=1;ind-=ind&(-ind)){
| ^~~
fortune_telling2.cpp: In function 'long long int getans(long long int)':
fortune_telling2.cpp:17:6: warning: statement has no effect [-Wunused-value]
17 | for(ind;ind<=m;ind++){
| ^~~
fortune_telling2.cpp: At global scope:
fortune_telling2.cpp:39:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
39 | main(){
| ^
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:61:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i=0;i<q.size();i++){
| ~^~~~~~~~~
fortune_telling2.cpp:66:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int i=0;i<V.size();i++){
| ~^~~~~~~~~
fortune_telling2.cpp:67:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | while(l+1<q.size() && q[l+1].f>=V[i].f) l++,update(q[l].s);
| ~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
