#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
int n, m;
const int maxn = 2e5+5;
struct node
{
int val;
node *left, *right;
node(int a, node *b, node *c)
{
val = a;
left = b;
right = c;
}
node* insert(int x, int L = 0, int R = m-1)
{
if(L<= x && x<= R)
{
if(L == R) return new node(val+1, NULL, NULL);
int M = (L+R)/2;
return new node(val+1, left->insert(x, L, M), right->insert(x, M+1, R));
}
return this;
}
int ask(int i, int j, int L = 0, int R = m-1)
{
if(i> R || j< L) return 0;
if(i<= L && R<= j) return val;
int M = (L+R)/2;
int x = left->ask(i, j, L, M);
int y = right->ask(i, j, M+1, R);
return x+y;
}
};
node* zero = new node(0, NULL, NULL);
int A[maxn], B[maxn];
int op[maxn];
node* ps[maxn];
vector< ii > foo;
int main()
{
scanf("%d %d", &n, &m);
for(int i = 1; i<= n; i++) scanf("%d %d", &A[i], &B[i]);
zero->left = zero->right = zero;
for(int i = 0; i< m; i++)
{
scanf("%d", &op[i]);
foo.pb(ii(op[i], i));
}
sort(foo.begin(), foo.end());
ps[m] = zero;
for(int i = m-1; i>= 0; i--)
{
ps[i] = ps[i+1];
ps[i] = ps[i]->insert(foo[i].Y);
// printf("insert %d\n", foo[i].Y);
}
ll ans = 0;
for(int i = 1; i<= n; i++)
{
int a = A[i], b = B[i];
if(a> b) swap(a, b);
int pa = lower_bound(foo.begin(), foo.end(), ii(a, 0))-foo.begin();
int pb = lower_bound(foo.begin(), foo.end(), ii(b, 0))-foo.begin();
// printf("pa pb %d %d\n", pa, pb);
int lo = 0, hi = m-1;
while(lo< hi)
{
int mid = (lo+hi+1)/2;
if((ps[pa])->ask(mid, m-1) == (ps[pb])->ask(mid, m-1)) hi = mid-1;
else lo = mid;
}
// printf("lo = %d\n", lo);
if(ps[pa]->ask(lo, m-1) != ps[pb]->ask(lo, m-1))
{
int swaps = ps[pa]->ask(0, m-1);
if(swaps%2) ans += B[i];
else ans += A[i];
continue;
}
int swaps = ps[pa]->ask(lo+1, m-1);
// printf("swaps %d\n", swaps);
if(swaps%2) ans += a;
else ans += b;
}
printf("%lld\n", ans);
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:56:7: 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:57:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i<= n; i++) scanf("%d %d", &A[i], &B[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &op[i]);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
