#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define debug(x) cout << #x << "= " << x << ", "
#define ll long long
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define SZ(x) (int) x.size()
#define wall cout << endl;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e5 + 10;
int n , k , ar[maxn];
pair<int , int> all[maxn];
bool last[maxn];
struct nod{
vector <int> all;
} tree[(maxn << 2)];
void Build(int node = 1 , int nl = 0 , int nr = k)
{
if(nr - nl == 1)
{
tree[node].all.pb(ar[nl]);
return;
}
int lc = node << 1 , rc = lc | 1 , mid = (nl + nr) >> 1;
Build(lc , nl , mid); Build(rc , mid , nr);
tree[node].all = tree[lc].all;
for(auto u : tree[rc].all) tree[node].all.pb(u);
sort(tree[node].all.begin() , tree[node].all.end());
}
bool check(int node , int l , int r)
{
if(tree[node].all.back() < l) return false;
int ps = lower_bound(tree[node].all.begin() , tree[node].all.end() , l) - tree[node].all.begin();
return tree[node].all[ps] < r;
}
int Find_ps(int l , int r , int node = 1 , int nl = 0 , int nr = k)
{
if(nr - nl == 1) return nl;
int lc = node << 1 , rc = lc | 1 , mid = (nl + nr) >> 1;
if(check(rc , l , r)) return Find_ps(l , r , rc , mid , nr);
else return Find_ps(l , r , lc , nl , mid);
}
int Get(int ind , int val , int node = 1 , int nl = 0 , int nr = k)
{
if(nr <= ind) return 0;
if(nl >= ind)
{
int ps = lower_bound(tree[node].all.begin() , tree[node].all.end() , val) - tree[node].all.begin();
return SZ(tree[node].all) - ps;
}
int lc = node << 1 , rc = lc | 1 , mid = (nl + nr) >> 1;
return Get(ind , val , lc , nl , mid) + Get(ind , val , rc , mid , nr);
}
int32_t main()
{
fast;
cin >> n >> k;
for(int i = 0 ; i < n ; i++) cin >> all[i].F >> all[i].S;
for(int i = 0 ; i < k ; i++) cin >> ar[i];
Build();
ll sum = 0;
for(int i = 0 ; i < n ; i++)
{
int l;
if(!check(1 , min(all[i].F , all[i].S) , max(all[i].F , all[i].S))) l = -1;
else l = Find_ps(min(all[i].F , all[i].S) , max(all[i].F , all[i].S));
int cnt = Get(l + 1 , all[i].S);
if(cnt & 1) swap(all[i].F , all[i].S);
sum += all[i].F;
}
cout << sum << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
