Submission #302775

#	Time	Username	Problem	Language	Result	Execution time	Memory
302775		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;
}
vector<pair<int, int>> arr;

int mini(int l, int r) {
	int ret = -1e9;
	while (l <= r) {
		chkmax(ret, arr[l++].second);
	}
	return ret;
}

void run() {
	int n, k;
	cin >> n >> k;
	for(int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}
	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 l = lower_bound(all(arr), make_pair(min(a[i], b[i]), 0)) - arr.begin();
		int r = lower_bound(all(arr), make_pair(max(a[i], b[i]), 0)) - arr.begin() - 1;
		if (l <= r) {
			if (get(arr[mini(l, r)].second + 1, n - 1, min(a[i], b[i])) & 1) ans += min(a[i], b[i]);
			else ans += max(a[i], b[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