#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define P pair<ll,ll>
using namespace std;
const int maxn = 200100;
ll tree[4*maxn], n, q;
ll a[maxn], b[maxn];
P t[maxn], tt[maxn];
vector<ll>tree_v[4*maxn];
void build(int li=0, int ri=q-1, int index=1) {
for(int i=li;i<=ri;i++) {
tree_v[index].pb(tt[i].first);
}
sort(tree_v[index].begin(), tree_v[index].end());
if(li == ri) {
tree[index] = t[li].second;
}
else {
int mid = (li + ri) / 2;
build(li,mid,2*index);
build(mid+1,ri,2*index+1);
tree[index] = max(tree[2*index], tree[2*index+1]);
}
}
ll find_ind(int ql, int qr, int li=0, int ri=q-1, int index=1) {
if(qr < ql) return -1;
if(li > qr || ri < ql) return -1;
else if(li >= ql && ri <= qr) return tree[index];
else {
int mid = (li + ri) / 2;
return max(find_ind(ql,qr,li,mid,2*index), find_ind(ql,qr,mid+1,ri,2*index+1));
}
}
// returns count of numbers in range [ql, qr] greater or equal to qval
ll query(int ql, int qr, ll qval, int li=0, int ri=q-1, int index=1) {
if(li > qr || ri < ql) return 0;
else if(li >= ql && ri <= qr) {
if(tree_v[index].size() == 0) return 0;
if(tree_v[index].back() < qval) return 0;
int ind = tree_v[index].size() - 1;
for(int cekor=tree_v[ind].size()/2;cekor>0;cekor/=2) {
while(ind-cekor>=0 && tree_v[index][ind-cekor] >= qval) ind -= cekor;
}
return tree_v[index].size() - ind;
}
else {
int mid = (li + ri) / 2;
return query(ql,qr,qval,li,mid,2*index) + query(ql,qr,qval,mid+1,ri,2*index+1);
}
}
int main() {
cin>>n>>q;
for(int i=1;i<=n;i++) {
cin>>a[i]>>b[i];
}
ll x;
for(int i=0;i<q;i++) {
cin>>t[i].first;
t[i].second = i;
tt[i] = t[i];
}
sort(t, t+q);
build();
ll result = 0LL;
for(int i=1;i<=n;i++) {
ll li = min(a[i], b[i]);
ll ri = max(a[i], b[i]);
ll ind = lower_bound(t, t+q, mp(li, -1LL)) - t;
ll ind2 = lower_bound(t, t+q, mp(ri, -1LL)) - t;
ll last_ind = find_ind(ind, ind2-1);
bool to_swap = false;
if(last_ind == -1) {
// count twos in whole array
ll cnt = query(0, q, ri);
to_swap = cnt % 2;
}
else {
// count twos in range [last_ind,
ll cnt = query(last_ind, q, ri);
to_swap = cnt % 2;
}
bool state = false;
if(a[i] > b[i]) state = false;
else state = true;
state |= to_swap;
if(state) result += li;
else result += ri;
}
cout<<result<<"\n";
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:64:8: warning: unused variable 'x' [-Wunused-variable]
ll x;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
19328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
19328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
19328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
