#include <bits/stdc++.h>
#define task "BriantheCrab"
#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define szf sizeof
#define sz(s) (int)((s).size())
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
template <class T> void minimize (T &t, T f) {if (t > f) t = f;}
template <class T> void maximize (T &t, T f) {if (t < f) t = f;}
const int maxN = 4e5 + 5;
const int inf = 1e18 + 7;
const int mod = 1e9 + 7;
// khong tu code thi khong kha len duoc dau
struct ST {
vector <int> st;
inline void init (int _n) {
st.resize (_n * 4, 0);
}
void upd (int id, int l, int r, int pos, int val) {
if (pos < l || pos > r) {
return;
}
if (l == r) {
maximize (st[id], val);
return;
}
int mid = (l + r) >> 1;
upd (id * 2, l, mid, pos, val);
upd (id * 2 + 1, mid + 1, r, pos, val);
st[id] = max (st[id * 2], st[id * 2 + 1]);
return;
}
int get (int id, int l, int r, int u, int v) {
if (v < l || u > r) {
return 0;
}
if (u <= l && r <= v) {
return st[id];
}
int mid = (l + r) >> 1;
int tL = get (id * 2, l, mid, u, v);
int tR = get (id * 2 + 1, mid + 1, r, u, v);
return max (tL, tR);
}
};
struct Fenwick {
vector <int> bit;
int n;
inline void init () {
bit.resize (n + 1, 0);
}
inline void upd (int id) {
for (; id < n; id += id & (-id)) {
//cout << id << ' ' << n << '\n';
bit[id] ++;
}
}
inline int get (int id) {
int res = 0;
for (; id; id -= id & (-id)) {
res += bit[id];
}
return res;
}
};
int n, k;
int a[maxN], b[maxN];
int aa[maxN], bb[maxN];
int res[maxN];
vector <int> pos[maxN];
vector <pii> cc[maxN];
pii que[maxN];
Fenwick Tf;
ST Ts;
void solve () {
cin >> n >> k;
vector <int> zip;
for (int i = 1; i <= n; i ++) {
cin >> a[i] >> b[i];
if (a[i] < b[i]) {
res[i] ++;
swap (a[i], b[i]);
}
aa[i] = a[i];
bb[i] = b[i];
zip.push_back (a[i]);
zip.push_back (b[i]);
}
for (int i = 1; i <= k; i ++) {
int t;
cin >> t;
que[i] = {t, i};
zip.push_back (t);
}
sort (all (zip));
zip.erase (unique (all (zip)), zip.end ());
for (int i = 1; i <= n; i ++) {
a[i] = lower_bound (all (zip), a[i]) - zip.begin () + 1;
b[i] = lower_bound (all (zip), b[i]) - zip.begin () + 1;
cc[a[i]].push_back ({b[i], i});
// cout << "ori " << aa[i] << ' ' << bb[i] << '\n';
// cout << a[i] << ' ' << b[i] << '\n';
}
for (int i = 1; i <= k; i ++) {
que[i].fi = lower_bound (all (zip), que[i].fi) - zip.begin () + 1;
pos[que[i].fi].push_back (que[i].se);
}
int lim = sz (zip) + 2;
Tf.n = k + 1;
Tf.init ();
Ts.init (lim);
for (int i = 1; i <= k; i ++) {
Ts.upd (1, 1, lim, que[i].fi, que[i].se);
//cout << "upd " << que[i].fi << ' ' << que[i].se << '\n';
}
//cout << "get " << Ts.get (1, 1, lim, 1, 4) << '\n';
for (int i = lim; i >= 1; i --) {
for (auto it : pos[i]) {
// if (i == 3) {
// cout << "gay " << it << '\n';
// }
Tf.upd (it);
}
for (auto [curB, id] : cc[i]) {
int rev = Ts.get (1, 1, lim, curB, i - 1);
// if (i == 4) {
// cout << "dmm " << rev << ' ' << curB << ' ' << Tf.get (k) << ' ' << Tf.get (rev) << '\n';
// }
if (rev == 0) {
res[id] += Tf.get (k);
}
else {
res[id] = Tf.get (k) - Tf.get (rev);
}
}
}
int ans = 0;
for (int i = 1; i <= n; i ++) {
//cout << res[i] << '\n';
//cout << (res[i] % 2 ? bb[i] : aa[i]) << ' ';
ans += (res[i] % 2 ? bb[i] : aa[i]);
}
cout << ans;
return;
}
signed main () {
cin.tie (nullptr) -> sync_with_stdio (false);
if (fopen (task".inp", "r")) {
freopen (task".inp", "r", stdin);
freopen (task".out", "w", stdout);
}
int t = 1;
//cin >> t;
while (t --) {
solve ();
}
return 0;
}
// thfv
Compilation message (stderr)
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:173:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
173 | freopen (task".inp", "r", stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:174:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
174 | freopen (task".out", "w", stdout);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |