| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 728212 | 2023-04-22T04:47:27 Z | jampm | Fortune Telling 2 (JOI14_fortune_telling2) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using ll = long long int;
#define all(a) a.begin(), a.end()
const int Mxn = 6e5 + 2;
struct segtree_sum {
vector<int> segs;
segtree_sum() {segs.assign(Mxn<<1, 0);}
void upd(int i, int x) {
i += Mxn; segs[i] += x;
for (i >>= 1; i; i >>= 1) {
segs[i] = segs[i<<1] + segs[i<<1|1];
}
}
int query(int l, int r, int ans = 0) {
for (l += Mxn, r += Mxn + 1; l < r; l >>= 1, r >>= 1) {
if (l&1) ans += segs[l++];
if (r&1) ans += segs[--r];
}
return ans;
}
};
struct segtree_max {
vector<int> segs;
segtree_max() {segs.assign(Mxn<<1, -1);}
void upd(int i, int x) {
i += Mxn; segs[i] = x;
for (i >>= 1; i; i >>= 1) {
segs[i] = max(segs[i<<1], segs[i<<1|1]);
}
}
int query(int l, int r, int ans = -1) {
for (l += Mxn, r += Mxn + 1; l < r; l >>= 1, r >>= 1) {
if (l&1) ans = max(segs[l++], ans);
if (r&1) ans = max(segs[--r], ans);
}
return ans;
}
};
struct query {
int idx, sufix, val;
bool operator<(const query & X) {return sufix > X.sufix;}
};
//stress test brute force
int brute_force(ll n, ll k, vector<pii> A, vector<int> B, ll ans = 0, ll idx = 0) {
ll n, k, ans = 0, idx = 0;
ll card[2][n], oper[k];
for (int i = 0; i < n; i++) card[0][i] = A[i].first, card[1][i] = A[i].second;
for (int i = 0; i < k; i++) cin >> oper[i];
for (int i = 0; i < n; i++, idx = 0) {
for (int j = 0; j < k; j++) {
idx ^= (card[idx][i] <= oper[j]);
}
ans += card[idx][i];
}
return ans;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, k, cnt = 0; cin >> n >> k;
ll ans = 0;
map<int, int> cc;
map<ll, ll> anti;
vector<pii> A(n);
for (auto &[x, y] : A) cin >> x >> y;
vector<int> T(k);
for (auto &e : T) cin >> e;
if (k < 40000 && n < 40000) {
cout << brute_borce(n, k, A, T) << '\n';
return 0;
}
for (auto [x, y] : A) cc[x], cc[y];
for (auto e : T) cc[e];
for (auto &[x, y] : cc) y = cnt++;
for (auto &[x, y] : A) x = cc[x], y = cc[y];
for (auto &e : T) e = cc[e];
for (auto [x, y] : cc) anti[y] = x;
segtree_max St_max;
vector<query> Count(n);
for (int i = 0; i < k; i++) {
St_max.upd(T[i], i);
}
for (int i = 0; i < n; i++) {
auto &[idx, sufix, val] = Count[i];
idx = i;
auto [l, r] = A[i];
if (l > r) {
sufix = St_max.query(r, l - 1);
val = l;
} else {
sufix = St_max.query(l, r - 1);
val = r;
}
}
sort(all(Count));
segtree_sum St_sum; vector<int> Ans(n);
for (int i = k - 1; i >= 0; i--) {
while (Count[cnt].sufix == i) {
auto &[idx, sufix, val] = Count[cnt++];
Ans[idx] = St_sum.query(val, Mxn - 1);
}
St_sum.upd(T[i], 1);
}
for (int i = 0; i < n; i++) {
auto [l, r] = A[i];
if (l > r) {
swap(l, r);
if (St_max.query(l, r - 1) == -1) {
if (St_sum.query(r, Mxn - 1)%2 == 1) ans += anti[l];
else ans += anti[r];
} else {
if (Ans[i]%2 == 1) ans += anti[l];
else ans += anti[r];
}
} else {
if (St_max.query(l, r - 1) == -1) {
if (St_sum.query(r, Mxn - 1)%2 == 1) ans += anti[r];
else ans += anti[l];
} else {
if (Ans[i]%2 == 1) ans += anti[l];
else ans += anti[r];
}
}
}
cout << ans << '\n';
}