// In the name of God
// Hope is last to die
#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
// #define int long long
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
const int maxn = 2e5 + 5, lg = 19;
const int inf = 1e9 + 7;
int n, q, rmq[maxn][lg], fen[maxn];
pii a[maxn], b[maxn];
bool cmp(pii x, pii y){
return max(x.F, x.S) > max(y.F, y.S);
}
void upd(int i){
for(i++; i <= q; i += i & -i) fen[i] += 1;
}
int get_(int i){
int res = 0;
for(i++; i; i &= i - 1) res += fen[i];
return res;
}
int get(int i){
return get_(q - 1) - get_(i);
}
int get_rmq(int l, int r){
int bit = 31 - __builtin_clz(r - l);
return max(rmq[l][bit], rmq[r - (1ll << bit)][bit]);
}
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q;
for(int i = 0; i < n ; i++) cin >> a[i].F >> a[i].S;
sort(a, a + n, cmp);
for(int i = 0; i < q; i++){
cin >> b[i].F;
b[i].S = i;
}
sort(b, b + q);
for(int i = q - 1; i >= 0; i--){
rmq[i][0] = b[i].S;
for(int bit = 1; bit < lg; bit++){
rmq[i][bit] = rmq[i][bit - 1];
if(i + (1ll << (bit - 1)) < n){
smax(rmq[i][bit], rmq[i + (1ll << (bit - 1))][bit - 1]);
}
}
}
int cur = q - 1;
ll ans = 0;
for(int i = 0; i < n; i++){
int mn = min(a[i].F, a[i].S), mx = a[i].F + a[i].S - mn;
while(cur >= 0 && b[cur].F >= mx) upd(b[cur--].S);
int j = lower_bound(b, b + q, mp(mn, 0)) - b;
int k = lower_bound(b, b + q, mp(mx, 0)) - b;
// cout << i << ' ' << a[i].F << ' ' << a[i].S << ' ' << j << ' ' << k << '\n';
if(j == q || b[j].F >= mx){
int x = get(-1);
// cout << x << '\n';
if(x % 2) ans += a[i].S;
else ans += a[i].F;
}
else{
int g = get_rmq(j, k);
int x = get(g);
if(x % 2) ans += mn;
else ans += mx;
}
}
cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
