#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define lb lower_bound
#define ub upper_bound
using ll = long long;
using ld = long double;
const int N = 6e5 + 7;
const ll mod = 1e9 + 7;
int n, k;
int act[N];
struct fenwick
{
int bit[N];
fenwick()
{
memset(bit, 0, sizeof bit);
}
void add(int x, int v)
{
++ x ;
for (; x < N; x += x & -x)
bit[x] += v;
}
int upto(int x)
{
++ x;
int ret = 0;
for (; x; x -= x & -x)
ret += bit[x];
return ret;
}
inline int get(int l, int r) { return upto(r) - upto(l - 1); }
} f1;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
cin >> n >> k;
vii a(n);
for (int i = 0; i < n; ++i)
cin >> a[i].f >> a[i].s;
vi b(k);
for (auto &u : b)
cin >> u;
vector<int> v;
for (auto u : a)
{
v.pb(u.f);
v.pb(u.s);
}
for (auto u : b)
v.pb(u);
sort(all(v));
v.erase(unique(all(v)), v.end());
for (int i = 0; i < sz(v); ++i)
{
act[i] = v[i];
}
auto get = [&](int x) -> int {
return lb(all(v), x) - v.begin();
};
for (int i = 0; i < n; ++i)
{
a[i].f = get(a[i].f);
a[i].s = get(a[i].s);
}
for (auto &u : b)
u = get(u);
sort(all(a), [&](pii x, pii y) {
return max(x.f, x.s) > max(y.f, y.s);
});
vii b2;
for (int i = 0; i < k; ++i)
{
b2.push_back({b[i], i});
}
sort(all(b2));
ll sum = 0 ;
for (int i = 0; i < n; ++i)
{
while (sz(b2) && b2.back().f >= a[i].f)
{
f1.add(b2.back().s , 1) ;
b2.pop_back();
}
int lst = -1 ;
int L = min(a[i].f , a[i].s) ;
int R = max(a[i].f , a[i].s) ;
for(int j = 0 ;j < k ;++ j){
if( b[j] >= L && b[j] < R ){
lst = j ;
}
}
if(~lst){
if(a[i].f < a[i].s) swap(a[i].f , a[i].s) ;
if(f1.get(lst + 1, N - 2)&1){
swap(a[i].f , a[i].s) ;
}
}else{
if(f1.get(0 , N - 2)&1){
swap(a[i].f , a[i].s) ;
}
}
sum += act[a[i].f] ;
}
cout << sum;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
