#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
const int mx=2e5+900;
const int mx2=1e6+9;
typedef long long ll;
const int mod=998244353 ;
const int SQ=400;
const ll inf=1e9+10;
vector<int>cord,q[mx];
int seg[4*mx],a[mx],b[mx],T[mx];
tree<int,null_type,greater_equal<int>,rb_tree_tag,tree_order_statistics_node_update> s;
int sz;int t;int n,k;
int combin(int x,int y){
if(t==0){
return (max(x,y));
}else{
return x+y;
}
}
void update(int node,int l,int r,int idx,int val){
if(l==idx){
seg[node]=val;
return;
}
int mid=(l+r)/2;
if(idx<=mid){
update(node*2,l,mid,idx,val);
}else{
update(node*2+1,mid+1,r,idx,val);
}
seg[node]=combin(seg[node*2],seg[node*2+1]);
return;
}
int query(int node,int l,int r,int left,int right){
if(r<left||l>right){
return -1;
}
if(l>=left&&r<=right){
return seg[node];
}
int mid=(l+r)/2;
return combin(query(node*2,l,mid,left,right),query(node*2+1,mid+1,r,left,right));
}
void upd(int pos,int val){
update(1,1,sz,pos,val);
}
int quer(int x,int y){
return query(1,1,sz,x,y);
}
int fin(int x){
//return upper_bound(cord.begin(),cord.end(),x)-cord.begin();
}
int main(){
cin>>n>>k;
T[0]=1;
for(int i=0;i<n;i++){
cin>>a[i]>>b[i];
cord.push_back(a[i]); cord.push_back(b[i]);
}
for(int i=0;i<k;i++){
cin>>T[i];
cord.push_back(T[i]);
}
sort(cord.begin(),cord.end()); cord.erase(unique(cord.begin() , cord.end()) , cord.end()) ;
sz=cord.size();
for(int i=0;i<n;i++){
a[i]=fin(a[i]);
b[i]=fin(b[i]);
}
memset(seg,-1,sizeof(seg));
for(int i=0;i<k;i++){
T[i]=fin(T[i]);
upd(T[i],i);
// cout<<T[i];
}
for(int i=0;i<n;i++){
int idx=quer(min(a[i],b[i]),max(a[i],b[i])-1);
q[idx+1].push_back(i);
}
t=1;ll ans=0;
memset(seg,0,sizeof(seg));
//return 0;
for (int i=k;i>=0;i--)
{
for (int j:q[i])
{
int parity;
//parity=quer(max(a[j],b[j]),sz)%2;
if(j==0){
parity^=(b[j]>a[j]);
}
ans+=parity ?(min(b[j],a[j])):(max(b[j],a[j]));
}
if(i!=k){upd(T[i],1);}
}
cout<<ans;
}
Compilation message
fortune_telling2.cpp: In function 'int fin(int)':
fortune_telling2.cpp:62:3: warning: no return statement in function returning non-void [-Wreturn-type]
62 | }
| ^
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:114:23: warning: 'parity' may be used uninitialized in this function [-Wmaybe-uninitialized]
114 | parity^=(b[j]>a[j]);
| ~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
