#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <time.h>
#include <stack>
#include <queue>
#include <random>
#include <fstream>
#define endl '\n'
#define flush fflush(stdout), cout.flush()
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define debug cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll hs = 199;
const ldb eps = 1e-9, pi = acos(-1);
using namespace std;
const int maxn = 200002;
struct wavelet {
int lo, hi;
vector<int> pr;
wavelet *l = 0, *r = 0;
wavelet(int *le, int *ri, int x, int y) {
lo = x, hi = y;
if (le < ri && lo < hi) {
int mid = lo + (hi - lo) / 2;
auto f = [&mid](int x) {
return x <= mid;
};
pr.reserve(ri - le + 1);
pr.push_back(0);
for (int *i = le; i != ri; i++)
pr.push_back(pr.back() + f(*i));
int *piv = stable_partition(le, ri, f);
l = new wavelet(le, piv, x, mid), r = new wavelet(piv, ri, mid + 1, y);
}
}
// count greater/equals than k in [l, r]
int cge(int l, int r, int k) {
if (l > r || hi < k) return 0;
if (lo >= k) return r - l + 1;
int le = pr[l - 1], ri = pr[r];
return this->l->cge(le + 1, ri, k) + this->r->cge(l - le, r - ri, k);
}
};
struct sparse {
int n;
vector<int> tree;
sparse(const int a[maxn], int size) {
n = size;
tree.resize(2 * n);
for (int i = 0; i < n; i++) tree[i + n - 1] = a[i];
for (int i = n - 2; i >= 0; i--)
tree[i] = max(tree[2 * i + 1], tree[2 * i + 2]);
}
int query(int l, int r) {
int rtn = -1e9;
for (l += n - 1, r += n - 1; l < r; l = (l - 1) / 2, r = (r - 1) / 2) {
if (!(l & 1)) rtn = max(rtn, tree[l++]);
if (r & 1) rtn = max(rtn, tree[r--]);
}
if (l == r) rtn = max(rtn, tree[l]);
return rtn;
}
};
int n, k, a[2][maxn], b[maxn], bb[maxn], c[maxn];
ll ans = 0;
bool cmp(const int &x, const int &y) {
return b[x] < b[y];
}
int lowerbound(const int &x) {
static int lo, hi, mid;
lo = 0, hi = n - 1;
while (lo < hi) {
mid = (lo + hi) >> 1;
if (b[c[mid]] < x) lo = mid + 1;
else hi = mid;
}
if (b[c[lo]] < x) lo++;
return lo;
}
int main() {
fast;
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[0][i] >> a[1][i];
for (int i = 0; i < k; i++) cin >> b[i];
for (int i = 0; i < k; i++) c[i] = i;
sort(c, c + k, cmp);
sparse sp = sparse(c, k);
for (int i = 0; i < maxn; i++) bb[i] = b[i];
wavelet w = wavelet(b, b + k, 1, 1e9);
for (int i = 0; i < maxn; i++) b[i] = bb[i];
for (int i = 0, mn, mx, lo, hi; i < n; i++) {
mn = min(a[0][i], a[1][i]);
mx = max(a[0][i], a[1][i]);
lo = lowerbound(mn), hi = lowerbound(mx) - 1;
if (lo > hi)
ans += a[w.cge(1, k, mx) & 1][i];
else
ans += a[w.cge(sp.query(lo, hi) + 2, k, mx) & 1][i];
}
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
32756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Memory limit exceeded |
453 ms |
262144 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
