Submission #256915

#	Time	Username	Problem	Language	Result	Execution time	Memory
256915		TeaTime	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	12 ms	19328 KiB

fortune_telling2

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>
#include <cmath>

using namespace std;

typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SIZE = 2e5 + 10, INF = 1e9 * 1e9;

vector<pair<ll, ll>> vec;
vector<ll> vc;
vector<ll> tree[SIZE * 4];

void build(int v, int l, int r) {
	if (l == r - 1) {
		tree[v].push_back(vc[l]);
	}
	else {
		int mid = (l + r) / 2;
		build(v * 2 + 1, l, mid);
		build(v * 2 + 2, mid, r);
		merge(tree[v * 2 + 1].begin(), tree[v * 2 + 1].end(), tree[v * 2 + 2].begin(), tree[v * 2 + 2].end(), std::back_inserter(tree[v]));
	}
}

ll get(int v, int l, int r, int askl, int askr, ll minVal, ll maxVal) {
	if (l >= askr || r <= askl) return 0;

	if (l >= askl && r <= askr) {
		ll mr = upper_bound(tree[v].begin(), tree[v].end(), maxVal) - tree[v].begin();
		ll lw = lower_bound(tree[v].begin(), tree[v].end(), minVal) - tree[v].begin();
		return mr - lw;
	}

	int mid = (l + r) / 2;
	return get(v * 2 + 1, l, mid, askl, askr, minVal, maxVal) + get(v * 2 + 2, mid, r, askl, askr, minVal, maxVal);
}

ll get2(int v, int l, int r, int askl, int askr, int minVal, int maxVal) {
	if (l == r - 1) {
		return l;
	}
	else {
		int mid = (l + r) / 2;
		ll mr = upper_bound(tree[v * 2 + 2].begin(), tree[v * 2 + 2].end(), maxVal) - tree[v * 2 + 2].begin();
		ll lw = lower_bound(tree[v * 2 + 2].begin(), tree[v * 2 + 2].end(), minVal) - tree[v * 2 + 2].begin();
		if (mr - lw >= 1) {
			return get2(v * 2 + 2, mid, r, askl, askr, minVal, maxVal);
		}
		else {
			return get2(v * 2 + 1, l, mid, askl, askr, minVal, maxVal);
		}
	}
}

int main() {
	fastInp;
	ll n, k;
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		ll a, b;
		cin >> a >> b;
		vec.push_back({ a, b });
	}

	vc.push_back(-1);
	for (int i = 0; i < k; i++) {
		ll x;
		cin >> x;

		vc.push_back(x);
	}

	build(0, 0, vc.size());

	ll s = 0;
	for (int i = 0; i < n; i++) {
		if (vec[i].first == vec[i].second) {
			s += vec[i].first;
			continue;
		}
		ll mn = min(vec[i].first, vec[i].second), mx = max(vec[i].first, vec[i].second);
		ll ind = get2(0, 0, vc.size(), 0, vc.size(), mn, mx - 1);
		
		if (ind == 0) {
			if (vec[i].first > vec[i].second) swap(vec[i].first, vec[i].second);
		}
		if (ind + 1 == vc.size()) {
			s += mx;
			continue;
		}
		ll cnt = get(0, 0, vc.size(), ind + 1, vc.size(), mx, INF);
		if (cnt % 2 == 0) {
			s += vec[i].first;
		}
		else {
			s += vec[i].second;
		}
	}

	cout << s;

	return 0;
}

//1 7
//2 9
//1
//4
//5
//9
//0
//12
//15

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:101:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ind + 1 == vc.size()) {
       ~~~~~~~~^~~~~~~~~~~~

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