#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
using namespace __gnu_pbds;
#define pow2(p) (1 << (p))
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
int n, k;
vector<int> a, b, t, flips;
void makePancakes() {
vector<int> t_sorted = t;
sort(t_sorted.begin(), t_sorted.end());
for (int i = 0; i < n; i++) {
flips[i] += t_sorted.end() -
lower_bound(t_sorted.begin(), t_sorted.end(), max(a[i], b[i]));
}
}
void adjustFlips() {
vector<pair<int, int>> tp(k);
for (int i = 0; i < k; i++) {
tp[i].first = t[i];
tp[i].second = i;
}
sort(tp.begin(), tp.end());
int st[k][20];
memset(st, 0, sizeof(st));
for (int i = 0; i < k; i++) {
st[i][0] = tp[i].second;
}
for (int j = 1; j < 20; j++) {
for (int i = 0; i + pow2(j) - 1 < k; i++) {
st[i][j] = max(st[i][j - 1], st[i + pow2(j - 1)][j]);
}
}
int log2[200005];
log2[1] = 0;
for (int i = 2; i < 200005; i++) {
log2[i] = log2[i / 2] + 1;
}
vector<pair<int, int>> p(n);
for (int i = 0; i < n; i++) {
p[i].second = i;
int l =
lower_bound(tp.begin(), tp.end(), make_pair(min(a[i], b[i]), -1)) - tp.begin();
int r =
lower_bound(tp.begin(), tp.end(), make_pair(max(a[i], b[i]), -1)) - tp.begin();
if (l == r) {
p[i].first = -1;
continue;
}
flips[i] += (b[i] > a[i]);
int len = r - l, j = log2[r - l];
p[i].first = max(st[l][j], st[l + len - pow2(j)][j]);
}
sort(p.begin(), p.end());
/*int ti = 0, pi = 0;
ordered_set os;
while (ti < k) {
os.insert({t[ti], ti});
while (pi < n and p[pi].first == ti) {
flips[p[pi].second] -= os.size() - os.order_of_key({max(a[p[pi].second], b[p[pi].second]), -1});
pi++;
}
ti++;
}*/
for (auto [c, i] : p) {
for (int j = 0; j < c; j++) {
if (max(a[i], b[i]) <= t[j]) flips[i]--;
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
a.resize(n), b.resize(n), flips.resize(n);
t.resize(k);
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
}
for (int i = 0; i < k; i++) {
cin >> t[i];
}
makePancakes();
adjustFlips();
long long ans = 0;
for (int i = 0; i < n; i++) {
if (flips[i] % 2) ans += b[i];
else ans += a[i];
}
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
