#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2 * 100100, MAXK = 2 * 100100, MAXA = 1e9 + 1e4;
int n, k, a[MAXN], b[MAXN], t[MAXK];
long long ans = 0;
struct no
{
int cnt;
no *l, *r;
no(int cnt = 0) : cnt(cnt), l(nullptr), r(nullptr)
{}
};
inline int getcnt(no* n) { return (n ? n->cnt : 0); }
no* upd(no* n, int beg, int end, int pos, int val)
{
if(beg == end)
return new no(getcnt(n) + val);
no* ans = (n ? new no(*n) : new no());
int mid = (beg + end) >> 1;
if(pos <= mid)
ans->l = upd(ans->l, beg, mid, pos, val);
else
ans->r = upd(ans->r, mid + 1, end, pos, val);
ans->cnt = getcnt(ans->l) + getcnt(ans->r);
return ans;
}
int get(no* n, int beg, int end, int pos)
{
if(!n)
return 0;
int mid = (beg + end) >> 1;
if(mid < pos)
return get(n->r, mid + 1, end, pos);
return get(n->l, beg, mid, pos) + getcnt(n->r);
}
no* pseg[MAXN];
int bs(int x, int y)
{
if(x > y)
swap(x, y);
int beg = 0, end = k, mid, p, q;
while(beg < end)
{
mid = (beg + end + 1) >> 1;
p = get(pseg[end], 1, MAXA, x - 1) - get(pseg[end], 1, MAXA, y - 1);
q = get(pseg[mid - 1], 1, MAXA, x - 1) - get(pseg[mid - 1], 1, MAXA, y - 1);
// dbg(beg, mid, end, p, q);
if(p - q > 0)
beg = mid;
else end = mid - 1;
}
return end;
}
int main()
{
scanf("%d %d", &n, &k);
pseg[0] = nullptr;
for(int i = 1; i <= n; ++i)
scanf("%d %d", &a[i], &b[i]);
for(int i = 1; i <= k; ++i)
scanf("%d", &t[i]), pseg[i] = upd(pseg[i - 1], 1, MAXA, t[i], 1);
for(int i = 1, j, swapped; i <= n; ++i)
{
for(j = k; j >= 1; --j)
if(min(a[i], b[i]) <= t[j] && t[j] < max(a[i], b[i]))
break;
// j = bs(a[i], b[i]);
if(min(a[i], b[i]) <= t[j] && t[j] < max(a[i], b[i]))
swapped = (b[i] > a[i]);
swapped += get(pseg[k], 1, MAXA, max(a[i], b[i]) - 1) - get(pseg[j], 1, MAXA, max(a[i], b[i]) - 1);
// printf("%d ", (swapped % 2 ? b : a)[i]);
ans += (swapped % 2 ? b : a)[i];
}
printf("%lld\n", ans);
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:64:7: 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:67:8: 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:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &t[i]), pseg[i] = upd(pseg[i - 1], 1, MAXA, t[i], 1);
~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:78:11: warning: 'swapped' may be used uninitialized in this function [-Wmaybe-uninitialized]
swapped += get(pseg[k], 1, MAXA, max(a[i], b[i]) - 1) - get(pseg[j], 1, MAXA, max(a[i], b[i]) - 1);
~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1408 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1408 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1408 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
1280 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1408 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1408 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1408 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
1280 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1408 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1408 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1408 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
1280 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
