Submission #302766

#	Time	Username	Problem	Language	Result	Execution time	Memory
302766		hexan	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	1 ms	384 KiB

fortune_telling2

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

typedef long long ll;
typedef long double ld;

#define all(x) (x).begin(), (x).end()
#define size(x) (ll)x.size()
#define x first
#define y second
#define chkmax(x, y) x = max(x, y)
#define chkmin(x, y) x = min(x, y)
 
const int N = 2e5 + 1;
int a[N], b[N], t[N];

int get(int l, int r, int x) {
	int ret = 0;
	while (l <= r) {
		ret += (t[l++] >= x);
	}
	return ret;
}

void run() {
	int n, k;
	cin >> n >> k;
	for(int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}
	vector<pair<int, int>> arr;
	for(int i = 0; i < k; i++) {
		cin >> t[i];
		arr.emplace_back(t[i], i);
	}
	sort(all(arr));
	ll ans = 0;
	for(int i = 0; i < n; i++) {
		int pos = lower_bound(all(arr), make_pair(max(a[i], b[i]), 0)) - arr.begin() - 1;
		if (pos == -1) continue;
		if (min(a[i], b[i]) <= arr[pos].first && arr[pos].first < max(a[i], b[i])) {
			if (a[i] < b[i]) swap(a[i], b[i]);
			if (get(arr[pos].second + 1, n - 1, max(a[i], b[i])) & 1) ans += b[i];
			else ans += a[i];
		} else {
			if (get(0, n - 1, a[i]) & 1) ans += b[i];
			else ans += a[i];
		}
	}

	cout << ans;
}

int main() {
#ifdef LOCAL
	freopen("input", "r", stdin);
	freopen("output", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	run();
}

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