#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 2e5+10, inf = 0x3f3f3f3f;
struct PersistentSegmentTree {
struct Node {
Node *l, *r;
int val;
Node() : l(this), r(this), val(0) {}
};
int t = 0;
Node *root[maxn]; // we have a root for each version of the seg
PersistentSegmentTree() { root[0] = new Node(); }
void upd(int pos) {
++t;
root[t] = upd(root[t-1], 1, inf, pos);
}
Node* upd(Node *node, int i, int j, int pos) { // add v to interval l, r
/* printf("%d %d\n", i, j);
fflush(stdout); */
Node *aq = new Node();
*aq = *node;
aq->val++;
if(i == j) return aq;
int m = (i+j) >> 1;
if(pos <= m)
aq->l = upd(aq->l, i, m, pos);
else
aq->r = upd(aq->r, m+1, j, pos);
return aq;
}
int query(Node *node, int i, int j, int l, int r) { // query the interval [l, r] on this version of the seg
if(i > r || j < l) return 0;
if(i >= l && j <= r) return node->val;
int m = (i+j) >> 1;
return query(node->l, i, m, l, r) + query(node->r, m+1, j, l, r);
}
int last(Node *L, Node *R, int i, int j) {
if(R->val - L->val == 0) return 0; // trocar pra 0 DEBUG <----------------------------------------->
if(i == j) return i;
int m = (i+j) >> 1;
int qr = last(L->r, R->r, m+1, j);
if(qr != 0) return qr; // trocar pra 0 DEBUG <----------------------------------------------------->
return last(L->l, R->l, i, m);
}
} segX, segTime;
int A[maxn], B[maxn];
pair<int,int> X[maxn];
int main() {
int n, k; scanf("%d %d", &n, &k);
for(int i = 1; i <= n; i++)
scanf("%d %d", A+i, B+i);
for(int i = 1; i <= k; i++) {
int x; scanf("%d", &x); X[i] = {x, i};
segTime.upd(x);
}
sort(X+1, X+k+1);
for(int i = 1; i <= k; i++) {
segX.upd(X[i].second);
}
long long ans = 0;
for(int i = 1; i <= n; i++) {
int a = A[i], b = B[i];
if(a > b) swap(a, b);
// quero achar o evento com o maior tempo tal que o valor dele está contido em [a, b[
int last = 0;
if(a != b) {
int itL = (lower_bound(X+1, X+1+k, pair<int,int>(a, 0)) - X) - 1;
int itR = (lower_bound(X+1, X+1+k, pair<int,int>(b, 0)) - X) - 1;
// printf("%d %d -> %d %d\n", a, b, itL, itR);
last = segX.last(segX.root[itL], segX.root[itR], 1, inf);
} else last = 0;
/* printf("%d %d -> %d %d %d\n", a, b, last, segTime.query(segTime.root[segTime.t], 1, inf, b, inf), segTime.query(segTime.root[segTime.t], 1, inf, b, inf) -
segTime.query(segTime.root[last], 1, inf, b, inf)); // >= b */
if(last != 0)
ans += segTime.query(segTime.root[segTime.t], 1, inf, b, inf) -
segTime.query(segTime.root[last], 1, inf, b, inf) % 2 == 0 ? b : a;
/* printf("%d\n", segTime.query(segTime.root[segTime.t], 1, inf, b, inf) -
segTime.query(segTime.root[last], 1, inf, b, inf) % 2 == 0 ? b : a); */
else
ans += segTime.query(segTime.root[segTime.t], 1, inf, b, inf) % 2 == 0 ? A[i] : B[i];
// printf("%d\n", segTime.query(segTime.root[segTime.t], 1, inf, b, inf) % 2 == 0 ? A[i] : B[i]);
}
printf("%lld\n", ans);
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:66:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | int n, k; scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | scanf("%d %d", A+i, B+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:72:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | int x; scanf("%d", &x); X[i] = {x, i};
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
