#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define endl '\n'
using namespace std;
const int maxn = 2e5 + 3;
int n, k;
pair <int, int> a[maxn];
int t[maxn];
void read()
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i].first >> a[i].second;
for (int i = 1; i <= k; i++)
cin >> t[i];
}
int tr[maxn * 8];
void merge(int v)
{
tr[v] = max(tr[v * 2], tr[v * 2 + 1]);
}
void update(int v, int l, int r, int pos, int val)
{
if (l == r)
{
tr[v] = max(tr[v], val);
return;
}
int mid = (l + r) / 2;
if (pos <= mid)
update(v * 2, l, mid, pos, val);
else
update(v * 2 + 1, mid + 1, r, pos, val);
merge(v);
}
int get(int v, int l, int r, int ll, int rr)
{
if (l > rr || r < ll || ll > rr)
return 0;
if (l >= ll && r <= rr)
return tr[v];
int mid = (l + r) / 2;
return max(get(v * 2, l, mid, ll, rr), get(v * 2 + 1, mid + 1, r, ll, rr));
}
int fenw[maxn * 2];
void update_fenw(int pos)
{
if (pos < 1)
return;
for (; pos <= 2 * n; pos += pos & -pos)
fenw[pos]++;
}
int get_pr(int pos)
{
int ans = 0;
for (; pos >= 1; pos -= pos & -pos)
ans += fenw[pos];
return ans;
}
vector <int> v;
vector <int> queries[maxn * 2];
int id[maxn];
void solve()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= k; j++)
if (t[j] >= min(a[i].first, a[i].second) && t[j] < max(a[i].first, a[i].second))
id[i] = j;
v.push_back(a[i].first);
v.push_back(a[i].second);
}
sort (v.begin(), v.end());
for (int i = 1; i <= k; i++)
{
int pos = lower_bound(v.begin(), v.end(), t[i]) - v.begin();
if (pos != 2 * n && v[pos] == t[i])
t[i] = pos + 1;
else
t[i] = pos;
update(1, 1, 2 * n, t[i], i);
}
for (int i = 1; i <= n; i++)
{
int f = lower_bound(v.begin(), v.end(), a[i].first) - v.begin() + 1, s = lower_bound(v.begin(), v.end(), a[i].second) - v.begin() + 1;
queries[get(1, 1, 2 * n, min(f, s), max(f, s) - 1)].push_back(i);
}
long long ans = 0;
for (int i = k; i >= 0; i--)
{
for (auto j: queries[i])
{
int curr_pos = lower_bound(v.begin(), v.end(), max(a[j].first, a[j].second)) - v.begin() + 1;
int cnt = k - i - get_pr(curr_pos-2);
if (i == 0)
ans += (cnt & 1) ? (long long)a[j].second : (long long)a[j].first;
else
ans += (cnt & 1) ? (long long)min(a[j].first, a[j].second) : (long long)max(a[j].first, a[j].second);
}
if (i != 0)
update_fenw(t[i]);
}
cout << ans << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
read();
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
