Submission #256062

#	Time	Username	Problem	Language	Result	Execution time	Memory
256062		islingr	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	224 ms	6396 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)

const int N = 1 << 18, inf = 2e9;
int mn[N << 1]; bool s[N << 1];

int q, p, x;
void upd(int v, int l, int r) {
	if (r - l == 1) return mn[v] = x, void(s[v] = 1);
	int m = (l + r) >> 1;
	if (p < m) upd(v << 1, l, m);
	else upd(v << 1|1, m, r);
	mn[v] = min(mn[v << 1], mn[v << 1|1]);
	s[v] = s[v << 1] ^ s[v << 1|1];
}
void upd(int a, int b) { p = a; x = b; upd(1, 0, q); }

int find(int v, int l, int r) {
	if (x <= mn[v]) return 0;
	if (r - l == 1) return r;
	int m = (l + r) >> 1;
	int res = find(v << 1|1, m, r);
	if (res) return res;
	return find(v << 1, l, m);
}
int find(int a) { x = a; return find(1, 0, q); }

int lo, hi;
bool sum(int v, int l, int r) {
	if (hi <= l || r <= lo) return 0;
	if (lo <= l && r <= hi) return s[v];
	int m = (l + r) >> 1;
	return sum(v << 1, l, m) ^ sum(v << 1|1, m, r);
}
bool sum(int l, int r) { lo = l; hi = r; return sum(1, 0, q); }

array<int, 2> a[N];
int t[N], ord[N];

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	fill(mn, mn + 2 * N, inf);
	int n; cin >> n >> q;
	rep(i, 0, n) cin >> a[i][0] >> a[i][1];
	rep(i, 0, q) cin >> t[i], ord[i] = i;
	sort(a, a + n, [](const auto &x, const auto &y) { return min(x[0], x[1]) > min(y[0], y[1]); });
	sort(ord, ord + q, [&](int x, int y) { return t[x] > t[y]; });
	int64_t ans = 0;
	for (int i = 0, j = 0; i < n; ++i) {
		bool b = 0; if (a[i][0] < a[i][1]) swap(a[i][0], a[i][1]), b = 1;
		while (j < q && a[i][1] <= t[ord[j]]) upd(ord[j], t[ord[j]]), ++j;
		int p = find(a[i][0]);
		ans += a[i][(!p && b) ^ sum(p, q)];
	}
	cout << ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65