Submission #30871

#	Time	Username	Problem	Language	Result	Execution time	Memory
30871		Navick	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	603 ms	20928 KiB

fortune_telling2

#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 2e5 + 10, LOG = 20;

int n, k, a[N], b[N];
pii t[N];

int seg[LOG][N];


void build(int lg = 0, int s = 0, int e = k){
	if(e - s < 2){
		seg[lg][s] = t[s].S;
		return ;
	}
	int mid = (s + e)/2;
	build(lg + 1, s , mid);
	build(lg + 1, mid , e);
	merge(seg[lg + 1] + s, seg[lg + 1] + mid, seg[lg + 1] + mid, seg[lg + 1] + e, seg[lg] + s);
}

int get_max(int lg ,int L, int R, int s = 0, int e = k){
	if(L<=s && e<=R){
		return seg[lg][e - 1];
	}
	if(L>=e || s>=R)return -1;
	int mid = (s + e)/2;
	return max(get_max(lg + 1, L, R, s, mid), get_max(lg + 1, L, R, mid, e));
}

int get_cnt(int lg, int vl, int L, int R, int s = 0, int e = k){
	if(L<=s && e<=R){
		return (e - s) - (upper_bound(seg[lg] + s, seg[lg] + e, vl) - (seg[lg] + s));
	}
	if(L>=e || s>=R)return 0;
	int mid = (s + e)/2;
	return get_cnt(lg + 1, vl, L, R, s, mid) + get_cnt(lg + 1, vl, L, R, mid, e);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	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].F; t[i].S = i;
	}

	sort(t, t + k);

	build();

	ll sum = 0;

	for(int i=0; i<n; i++){
		bool turn;
		if(a[i] < b[i])turn = true;
		else turn = false;
		int lo = lower_bound(t, t + k, pii(min(a[i], b[i]), -1)) - t;
		int hi = lower_bound(t, t + k, pii(max(a[i], b[i]), -1)) - t;
		int tim = get_max(0, lo, hi);
		int xk = get_cnt(0, tim , hi, k);
		int delta = 0;
		if(turn){
			if(tim == -1)delta = xk;
			else delta = xk + 1;
		}else
			delta = xk;
		if(delta % 2 == 1)swap(a[i], b[i]);
		sum += a[i];
	}

	cout << sum << endl;
}

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