Submission #1032771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032771		juicy	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	215 ms	18876 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5, inf = 1e9;

int n, k;
int s[4 * N], sum[4 * N], lst[N];
bool flip[N];

void upd(int i, int x, int id = 1, int l = 1, int r = k) {
	if (l == r) {
		s[id] = x;
		sum[id] = x != inf;
		return;
	}
	int md = (l + r) / 2;
	if (i <= md) {
		upd(i, x, id * 2, l, md);
	} else {
		upd(i, x, id * 2 + 1, md + 1, r);
	}
	s[id] = min(s[id * 2], s[id * 2 + 1]);
	sum[id] = sum[id * 2] + sum[id * 2 + 1];
}

int qry(int u, int v, int id = 1, int l = 1, int r = k) {
	if (u <= l && r <= v) {
		return sum[id];
	}
	int md = (l + r) / 2;
	if (v <= md) {
		return qry(u, v, id * 2, l, md);
	}
	if (md < u) {
		return qry(u, v, id * 2 + 1, md + 1, r);
	}
	return qry(u, v, id * 2, l, md) + qry(u, v, id * 2 + 1, md + 1, r);
}

int walk(int x, int id = 1, int l = 1, int r = k) {
	if (l == r) {
		return l;
	}
	int md = (l + r) / 2;
	if (s[id * 2 + 1] < x) {
		return walk(x, id * 2 + 1, md + 1, r);
	}
	return walk(x, id * 2, l, md);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	cin >> n >> k;
	vector<array<int, 3>> pt;
	for (int i = 1; i <= n; ++i) {
		int a, b; cin >> a >> b;
		if (a < b) {
			swap(a, b);
			flip[i] = 1;
		}
		pt.push_back({a, b, i});
	}
	vector<array<int, 2>> ope;
	for (int i = 0; i < k; ++i) {
		int x; cin >> x;
		ope.push_back({x, i + 1});
	}
	sort(ope.rbegin(), ope.rend());
	sort(pt.begin(), pt.end(), [&](auto a, auto b) {
		return a[1] > b[1];
	});
	fill(lst + 1, lst + n + 1, 1);
	auto reset = [&]() {
		for (int i = 1; i <= k; ++i) {
			upd(i, inf);
		}
	};
	reset();
	int j = 0;
	for (auto [a, b, id] : pt) {
		while (j < k && ope[j][0] >= b) {
			upd(ope[j][1], ope[j][0]);
			++j;
		}
		if (s[1] < a) {
			lst[id] = walk(a) + 1;
		}
	}
	sort(pt.rbegin(), pt.rend());
	j = 0;
	long long res = 0;
	reset();
	for (auto [a, b, id] : pt) {
		while (j < k && ope[j][0] >= a) {
			upd(ope[j][1], ope[j][0]);
			++j;
		}
		if (lst[id] > k) {
			res += a;
		} else {
			int iter = qry(lst[id], k) % 2;
			array<int, 2> s = {a, b};
			if (flip[id]) {
				swap(s[0], s[1]);
			}
			if (lst[id] != 1 && s[0] == b) {
				swap(s[0], s[1]);
			}
			res += s[iter];
		}
	}
	cout << res;
	return 0;
}

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