#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
typedef pair<int, int> ii;
typedef long long ll;
const int len = 2e5+5, mx = 1e9;
ii arr[len];
int num[len], n, m;
struct node{
int sum;
node *left, *right;
node(int s = 0, node *l = NULL, node *r = NULL){
sum = s;
left = l;
right = r;
}
};
typedef node* pnode;
pnode suf[len], null = new node();
pnode add(pnode t, int l, int r, int i){
if (l == r)
return new node(t->sum+1, null, null);
int mid = (l+r)/2;
if (i <= mid)
return new node(t->sum+1, add(t->left, l, mid, i), t->right);
return new node(t->sum+1, t->left, add(t->right, mid+1, r, i));
}
int ask(pnode t, int l, int r, int i, int j){
if (r < i || j < l)
return 0;
if (i <= l && r <= j)
return t->sum;
int mid = (l+r)/2;
return ask(t->left, l, mid, i, j)+ask(t->right, mid+1, r, i, j);
}
int bs(int a, int b){
if (a > b)
return 0;
int l = 1, r = n, ans = 0;
while (l <= r){
int mid = (l+r)/2;
if (ask(suf[mid], 1, mx, a, b) > 0)
ans = mid, l = mid+1;
else
r = mid-1;
}
return ans;
}
int main(){
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d %d", &arr[i].fi, &arr[i].se);
for (int i = 1; i <= m; i++)
scanf("%d", &num[i]);
suf[m+1] = null->left = null->right = null;
for (int i = m; i >= 1; i--)
suf[i] = add(suf[i+1], 1, mx, num[i]);
ll ans = 0;
for (int i = 1; i <= n; i++){
int l = arr[i].fi, r = arr[i].se;
int pos = bs(min(l, r), max(l, r)-1);
int cnt = ask(suf[pos+1], 1, mx, max(l, r), mx);
if (pos == 0){
if (cnt%2 == 0)
ans += l;
else
ans += r;
}
else{
if (cnt%2 == 0)
ans += max(l, r);
else
ans += min(l, r);
}
}
printf("%lld\n", ans);
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &arr[i].fi, &arr[i].se);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &num[i]);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
