#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx,avx2,bmi")
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define prec fixed<<setprecision
#define endl '\n'
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define fout(name) freopen(name".out", "w", stdout);
using namespace std;
const int maxN=6e5+69;
const int mod=1e9+7;
const int bs=448;
ll n,q,a[maxN],b[maxN],c[maxN],BIT[maxN*3],st[20][maxN*3];
ll lg2(ll x){return x?__builtin_clzll(1)-__builtin_clzll(x):-1;}
void update(ll x,ll v){if(x==0)BIT[0]+=v,x++;for(;x<maxN;x+=x&-x)BIT[x]+=v;}
ll get(ll x){
if(x<0)return 0;
ll r=BIT[0];
for(;x;x-=x&-x)r+=BIT[x];
return r;
}
ll getmax(ll L,ll R){
if(L>R)return -1;
ll i = lg2(R - L + 1);
return max(st[i][L], st[i][R - (1 << i) + 1]);
}
vector<pll> v;
vector<ll> d;
vector<ll> query[maxN];
ll ans[maxN];
void Enter(){
cin>>n>>q;
for(int i=0;i<n;i++)cin>>a[i]>>b[i],d.pb(a[i]),d.pb(b[i]);
for(int i=0;i<q;i++)cin>>c[i],d.pb(c[i]);
sort(all(d));
d.resize(unique(all(d))-d.begin());
for(int i=0;i<n;i++)a[i]=lower_bound(all(d),a[i])-d.begin();
for(int i=0;i<n;i++)b[i]=lower_bound(all(d),b[i])-d.begin();
for(int i=0;i<q;i++)c[i]=lower_bound(all(d),c[i])-d.begin();
memset(st,-1,sizeof st);
for(ll i=0;i<q;i++)st[0][c[i]]=max(st[0][c[i]],i);
for(int i=1;i<20;i++)
for(int j=0;j+(1<<i)<maxN*3;j++)
st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
for(int i=0;i<n;i++){
ll l=min(a[i],b[i]),r=max(a[i],b[i])-1,w=getmax(l,r);
if(w!=-1)ans[i]=a[i]<b[i];
else w=0;
//cout<<i<<" "<<w<<endl;
query[w].pb(i);
}
ll res=0;
for(int i=q-1;i>=0;i--){
update(c[i],1);
for(auto x:query[i]){
ll r=max(a[x],b[x])-1;
ans[x]^=(get(n*3)-get(r))%2;
if(ans[x])res+=d[b[x]];
else res+=d[a[x]];
}
}
cout<<res;
}
//amogus
signed main(){
open("seq198");
cin.tie(nullptr);ios_base::sync_with_stdio(NULL);
ll t=1;
//cin>>t;
while(t--)
Enter();
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:11:54: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
11 | #define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:71:5: note: in expansion of macro 'open'
71 | open("seq198");
| ^~~~
fortune_telling2.cpp:11:87: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
11 | #define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:71:5: note: in expansion of macro 'open'
71 | open("seq198");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
121 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
121 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
121 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
