Submission #231873

#	Time	Username	Problem	Language	Result	Execution time	Memory
231873		iefnah06	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	100 / 100	740 ms	28552 KiB

fortune_telling2

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

using ll = long long;

template <typename K, typename V, typename Comp = std::less<K>>
using order_statistic_map = __gnu_pbds::tree<
	K, V, Comp,
	__gnu_pbds::rb_tree_tag,
	__gnu_pbds::tree_order_statistics_node_update
>;

template <typename K, typename Comp = std::less<K>>
using order_statistic_set = order_statistic_map<K, __gnu_pbds::null_type, Comp>;

const int MAXN = 2.1e5;
const int MAXQ = 2.1e5;
int n, q;
int ca[MAXN];
int cb[MAXN];
int qt[MAXQ];

const int S = 1 << 19;
int seg[2 * S];

void update(int i, int v) {
	if (seg[S+i] >= v) return;
	seg[S+i] = v;
	for (int a = (S+i)/2; a; a /= 2) {
		seg[a] = max(seg[2*a], seg[2*a+1]);
	}
}

int query(int l) {
	int res = -1;
	for (int a = S+l, b = S+S; a < b; a /= 2, b /= 2) {
		if (a & 1) {
			res = max(res, seg[a++]);
		}
		if (b & 1) {
			res = max(res, seg[--b]);
		}
	}
	return res;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

	cin >> n >> q;
	vector<int> vals;
	for (int i = 0; i < n; i++) {
		cin >> ca[i] >> cb[i];
		vals.push_back(min(ca[i], cb[i]));
	}
	for (int i = 0; i < q; i++) {
		cin >> qt[i];
		vals.push_back(qt[i]);
	}

	sort(vals.begin(), vals.end());
	vals.erase(unique(vals.begin(), vals.end()), vals.end());
	auto lookup = [&](int v) {
		auto it = lower_bound(vals.begin(), vals.end(), v);
		assert(it != vals.end() && *it == v);
		return int(it - vals.begin());
	};

	vector<int> cards(n);
	iota(cards.begin(), cards.end(), 0);
	sort(cards.begin(), cards.end(), [&](int i, int j) {
		return max(ca[i], cb[i]) < max(ca[j], cb[j]);
	});
	vector<int> operations(q);
	iota(operations.begin(), operations.end(), 0);
	sort(operations.begin(), operations.end(), [&](int i, int j) {
		return qt[i] < qt[j];
	});

	order_statistic_set<pair<int, int>> os;
	for (int i = 0; i < q; i++) {
		os.insert({i, qt[i]});
	}
	auto operations_it = operations.begin();
	ll ans = 0;
	for (int a = 1; a < S*2; a++) {
		seg[a] = -1;
	}
	for (auto card : cards) {
		int lo = min(ca[card], cb[card]);
		int hi = max(ca[card], cb[card]);
		while (operations_it != operations.end() && qt[*operations_it] < hi) {
			os.erase({*operations_it, qt[*operations_it]});
			update(lookup(qt[*operations_it]), *operations_it);
			operations_it++;
		}

		int last_time = query(lookup(lo));
		int parity = (os.size() - os.order_of_key({last_time, -1})) % 2;
		if (last_time == -1) {
			ans += parity ? cb[card] : ca[card];
		} else {
			ans += parity ? lo : hi;
		}
	}
	cout << ans << '\n';

	return 0;
}

// Let's assume that a_i < b_i
// t_j < a_i: nothing happens
// a_i <= t_j < b_i: becomes b_i
// b_i <= t_j: flips
// For each card, let's fix the last operation of the second type, then the result only depends on the parity of (# of flips) after that operation

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