Submission #156535

#	Time	Username	Problem	Language	Result	Execution time	Memory
156535		Saboon	운세 보기 2 (JOI14_fortune_telling2)	C++14	100 / 100	601 ms	23616 KiB

fortune_telling2

#include <bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn = 2e5 + 4;
const int maxl = 23;

int seg[maxl][4 * maxn], t[maxn], a[maxn], b[maxn];

int get2 (int id, int L, int R, int l, int r, int lb, int h = 0) {
	if (L == l and R == r) {
		int fi = lower_bound (seg[h] + L, seg[h] + R, lb) - seg[h];
		return R - fi;
	}
	int mid = (L + R) >> 1, ret = 0;
	if (mid > l)
		ret += get2 (2 * id + 0, L, mid, l, min (mid, r), lb, h + 1);
	if (mid < r)
		ret += get2 (2 * id + 1, mid, R, max (l, mid), r, lb, h + 1);
	return ret;
}

int get (int id, int L, int R, int lb, int ub, int h = 0) {
	int idx = lower_bound (seg[h] + L, seg[h] + R, lb) - seg[h];
	if (idx == R or seg[h][idx] >= ub)
		return -1;
	if (L + 1 == R)
		return L;
	int mid = (L + R) >> 1;
	int ret = get (2 * id + 1, mid, R, lb, ub, h + 1);
	if (ret != -1)
		return ret;
	return get (2 * id + 0, L, mid, lb, ub, h + 1);
}

void build (int id, int L, int R, int h = 0) {
	if (L + 1 == R) {
		seg[h][L] = t[L];
		return;
	}
	int mid = (L + R) >> 1;
	build (2 * id + 0, L, mid, h + 1);
	build (2 * id + 1, mid, R, h + 1);
	
	for (int i = L; i < R; i++)
		seg[h][i] = seg[h + 1][i];
	sort (seg[h] + L, seg[h] + R);
}

int main () {
	ios::sync_with_stdio(false);
	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];
	build (1, 0, k);
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		int fi = a[i], se = b[i];
		if (fi == se) {
			ans += fi;
			continue;
		}
		if (fi > se)
			swap (fi, se);
		int idx = get (1, 0, k, fi, se);
		if (idx == -1) {
			int x = get2 (1, 0, k, 0, k, se);
			if (x % 2 == 0)
				ans += a[i];
			else
				ans += b[i];
		}
		else {
			int x = get2 (1, 0, k, idx, k, se);
			if (x % 2 == 0)
				ans += se;
			else
				ans += fi;
		}	
	}
	cout << ans << endl;
}

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