#include <bits/stdc++.h>
#define ll long long
#define ok puts("ok");
using namespace std;
const int N = (int)2e5 + 7;
struct T {
int tree[N * 4];
T() {
memset(tree, -1, sizeof tree);
}
void upd(int pos, int val, int v = 1, int tl = 0, int tr = 2e5) {
if (tl == tr) {
tree[v] = val;
return ;
}
int mid = (tl + tr) >> 1;
if (pos <= mid) {
upd(pos, val, v + v, tl, mid);
} else {
upd(pos, val, v + v + 1, mid + 1, tr);
}
tree[v] = max(tree[v + v], tree[v + v + 1]);
}
int get(int l, int r, int v = 1, int tl = 0, int tr = 2e5) {
if (tl > r || tr < l) return -1;
if (l <= tl && tr <= r) return tree[v];
int mid = (tl + tr) >> 1;
return max(get(l, r, v + v, tl, mid), get(l, r, v + v + 1, mid + 1, tr));
}
};
T tr;
struct fen {
int tree[N];
fen() {
memset(tree, 0, sizeof tree);
}
void upd(int pos, int val) {
while (pos < N) {
tree[pos] += val;
pos = pos | pos + 1;
}
}
int get(int r) {
int res = 0;
while (r >= 0) {
res += tree[r];
r = (r & r + 1) - 1;
}
return res;
}
};
fen bit1, bit2;
int n, k;
int flip[N];
int a[N], b[N], q[N], border[N];
ll sum = 0;
main() {
scanf("%d %d", &n, &k);
vector<int> vec;
for (int i = 1; i <= n; i++) {
scanf("%d %d", &a[i], &b[i]);
vec.push_back(a[i]);
vec.push_back(b[i]);
if (a[i] > b[i]) {
swap(a[i], b[i]);
flip[i] = 1;
}
}
for (int i = 1; i <= k; i++) {
scanf("%d", &q[i]);
}
sort(vec.begin(), vec.end());
vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
for (int i = 1; i <= n; i++) {
a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
b[i] = lower_bound(vec.begin(), vec.end(), b[i]) - vec.begin();
}
for (int i = 1; i <= k; i++) {
q[i] = upper_bound(vec.begin(), vec.end(), q[i]) - vec.begin() - 1;
tr.upd(q[i], i);
}
vector<pair<int, int>> v1;
for (int i = 1; i <= n; i++) {
border[i] = tr.get(a[i], b[i] - 1);
v1.push_back({border[i] + 1, i});
if (border[i] > 0) {
flip[i] = 1;
}
}
sort(v1.begin(), v1.end());
int sz = k;
for (int i = v1.size() - 1; i >= 0; i--) {
while (sz >= v1[i].first) {
bit1.upd(q[sz], 1);
sz--;
}
flip[v1[i].second] ^= ((k - sz - bit1.get(b[v1[i].second] - 1)) & 1);
}
for (int i = 1; i <= n; i++) {
sum += (flip[i] ? vec[b[i]] : vec[a[i]]);
}
printf("%lld\n", sum);
}
Compilation message
fortune_telling2.cpp: In member function 'void fen::upd(int, int)':
fortune_telling2.cpp:45:20: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
pos = pos | pos + 1;
~~~~^~~
fortune_telling2.cpp: In member function 'int fen::get(int)':
fortune_telling2.cpp:52:15: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
r = (r & r + 1) - 1;
~~^~~
fortune_telling2.cpp: At global scope:
fortune_telling2.cpp:64:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:65: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:68: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:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3043 ms |
4992 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3043 ms |
4992 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3043 ms |
4992 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
