Submission #372903

#	Time	Username	Problem	Language	Result	Execution time	Memory
372903		Ahoora	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	35 / 100	2324 ms	262148 KiB

fortune_telling2

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

const int N = 3 * 2 * 1000 * 100 + 10, LG = 20;
int n, k, a[N], b[N], t[N], kol[N];
unordered_map<int, int> fen[N];

void UPD(int id, int x) {
	kol[id]++;
	for (++x; x < N; x += x & -x)
		fen[id][x]++;
}

void upd(int x, int y) {
	for (++x; x < N; x += x & -x)
		UPD(x, y);
}

int GET(int id, int x) {
	int res = 0;
	for (; x; x -= x & -x)
		res += fen[id][x];
	return res;
}

int get(int x, int y) {
	int res = 0;
	for (; x; x -= x & -x)
		res += kol[x] - GET(x, y);
	return res;
}

inline int inp() {
	int res = 0;
	char c = '0';
	while (c >= '0' && c <= '9') {
		((res *= 10) += c - '0');
		c = getchar();
	}
	return res;
}

int main() { 
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	n = inp(), k = inp();
	vector<int> all;
	for (int i = 0; i < n; i++) {
		a[i] = inp(), b[i] = inp();
		for (auto x: {a[i], b[i]})
			all.push_back(x);
	}
	for (int i = 0; i < k; i++)
		t[i] = inp(), all.push_back(t[i]);
	sort(all.begin(), all.end());
	all.resize(unique(all.begin(), all.end()) - all.begin());
	for (int i = 0; i < n; i++)
		for (auto x: {&a[i], &b[i]})
			*x = lower_bound(all.begin(), all.end(), *x) - all.begin();
	for (int i = 0; i < k; i++)
		t[i] = lower_bound(all.begin(), all.end(), t[i]) - all.begin();
	reverse(t, t + k);
	for (int i = 0; i < k; i++)
		upd(i, t[i]);
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		int fl = 0;
		if (a[i] > b[i])
			fl++, swap(a[i], b[i]);
		int ind = 0;
		for (int j = LG - 1; j >= 0; j--) {
			if (ind + (1 << j) > k)
				continue;
			int id = ind + (1 << j);
			int x = GET(id, b[i]) - GET(id, a[i]); 
			if (x == 0) 
				ind += 1 << j;
		}
		int res = get(ind, b[i]);
		if (ind == k) {
			fl += res;
			ans += (fl & 1? all[b[i]]: all[a[i]]);
		}
		else {
			fl = 0;
			fl += res;
			swap(a[i], b[i]);
			ans += (fl & 1? all[b[i]]: all[a[i]]);
		}
	}
	printf("%lld\n", ans);
	return 0;
}

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