#include<bits/stdc++.h>
using namespace std;
const int mxn=2e5+1;
const int mx=3*mxn;
int tree[4*mx]={};
void update(int node,int b,int e,int p,int v) {
if(b>p || e<p)return;
if(b==e) {
tree[node]=v;
return;
}
int mid=b+e>>1;
int left=node<<1;
int right=left|1;
update(left,b,mid,p,v);
update(right,mid+1,e,p,v);
tree[node]=max(tree[left],tree[right]);
}
int query(int node,int b,int e,int l,int r) {
if(l>r)return -1;
if(b>r || e<l)return -1;
if(b>=l && e<=r)return tree[node];
int mid=b+e>>1;
int left=node<<1;
int right=left|1;
return max(query(left,b,mid,l,r),query(right,mid+1,e,l,r));
}
struct BIT {
int bit[mxn]={};
void update(int p,int v) {
for(;p>0;p-=p&-p)bit[p]+=v;
}
int query(int p,int s=0) {
for(;p<mxn;p+=p&-p)s+=bit[p];
return s;
}
};
int main() {
int n,k;
scanf("%d%d",&n,&k);
int a[n+1],b[n+1];
int qs[k+1];
vector<int> v;
long long ans[n+1];
for(int i=1;i<=n;i++) {
scanf("%d%d",&a[i],&b[i]);
v.push_back(a[i]);
v.push_back(b[i]);
ans[i]=a[i];
}
for(int i=1;i<=k;i++) {
scanf("%d",&qs[i]);
v.push_back(qs[i]);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
for(int i=1;i<=k;i++) {
qs[i]=lower_bound(v.begin(),v.end(),qs[i])-v.begin()+1;
update(1,1,mx,qs[i],i);
}
vector<int> td[k+2];
for(int i=1;i<=n;i++) {
int x=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
int y=lower_bound(v.begin(),v.end(),b[i])-v.begin()+1;
int rs=query(1,1,mx,min(x,y),max(x,y)-1);
if(rs<=0)continue;
ans[i]=max(a[i],b[i]);
td[rs+1].push_back(i);
}
BIT bt;
for(int i=k;i>0;i--) {
bt.update(qs[i],1);
for(int j:td[i]) {
int p=lower_bound(v.begin(),v.end(),max(a[j],b[j]))-v.begin()+1;
int r=bt.query(p);
if(r&1)ans[j]=ans[j]^a[j]^b[j];
}
}
long long res=0;
for(int i=1;i<=n;i++)res+=ans[i];
cout<<res<<endl;
}
Compilation message
fortune_telling2.cpp: In function 'void update(int, int, int, int, int)':
fortune_telling2.cpp:16:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=b+e>>1;
~^~
fortune_telling2.cpp: In function 'int query(int, int, int, int, int)':
fortune_telling2.cpp:31:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=b+e>>1;
~^~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&k);
~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a[i],&b[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&qs[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
1280 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
1280 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
1280 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
