Submission #36048

#	Time	Username	Problem	Language	Result	Execution time	Memory
36048		ToMoClone	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	35 / 100	2000 ms	93432 KiB

fortune_telling2

/*input
5 3
4 6
9 1
8 8
4 2
3 7
8 2 9
*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

const int N = 600005;

int bit[N], Last[N], On[N], Arr[N][20], n, k;
pair<int, int> Query[N], a[N];
map<int, int> Label;

void update(int index, int val){
	while(index < N) bit[index] += val, index += index & (-index);
}

int get(int index){
	int res = 0;
	while(index > 0) res += bit[index], index -= index & (-index);
	return res;
}

int Rmq(int l, int r){
	if(l > r) return 0;
	int dist = (int)log2(r - l + 1);
	return max(Arr[l][dist], Arr[r - (1 << dist) + 1][dist]);
}

int main(){
	cin >> n >> k;
	for(int i = 1; i <= n; ++i){
		cin >> a[i].first >> a[i].second;
		Label[a[i].first] = 1, Label[a[i].second] = 1;
	}
	sort(a + 1, a + n + 1, [&](pair<int, int> &x, pair<int, int> &y){
		if(max(x.first, x.second) != max(y.first, y.second))
			return max(x.first, x.second) < max(y.first, y.second);
		return min(x.first, x.second) < min(y.first, y.second);
	});

	for(int i = 1; i <= n; ++i){
		On[i] = (a[i].first > a[i].second);
		if(On[i] == 0) swap(a[i].first, a[i].second);
	}

	Query[k + 1] = make_pair(1000000007, 0);
	for(int i = 1; i <= k; ++i){
		cin >> Query[i].first;
		Query[i].second = i;
		Label[Query[i].first] = 1;
	}
	sort(Query + 1, Query + k + 1);

	int cnt = 0;
	for(auto it = Label.begin(); it != Label.end(); ++it)
		it->second = ++cnt;

	for(int i = 1; i <= k; ++i)
		Arr[Label[Query[i].first]][0] = Query[i].second;

	for(int j = 1; (1 << j) < N; ++j)
		for(int i = 1; i < N; ++i)
			Arr[i][j] = max(Arr[i][j - 1], Arr[min(i + (1 << (j - 1)), N - 1)][j - 1]);

	for(int i = 1; i <= n; ++i){
		int l = Label.lower_bound(a[i].second)->second;
		int r = (--Label.lower_bound(a[i].first))->second;
		Last[i] = Rmq(l, r);
	}

	int64_t l = 1, ans = 0;
	for(int i = 1; i <= n; ++i){
		while(Query[l].first < a[i].first) update(Query[l++].second, 1);
		if(Last[i] != 0) On[i] = 1 ^ ((k - Last[i] - (get(N - 1) - get(Last[i]))) & 1);
			else On[i] ^= (k - get(N - 1)) & 1;
		ans += On[i] ? a[i].first : a[i].second;
	}

	cout << ans << endl;
}

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