Submission #845990

#	Time	Username	Problem	Language	Result	Execution time	Memory
845990		LeonaRaging	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	35 / 100	1625 ms	175096 KiB

fortune_telling2

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

#define pb push_back
#define mp make_pair
#define SZ(val) (int)val.size()
#define all(val) val.begin(), val.end()

const int maxn = 5e5 + 4;

int n, k, a[maxn], b[maxn], q[maxn], idx[maxn], node[maxn], L[maxn], R[maxn], bst[maxn];
vector<int> vals, que[maxn];

struct seg_tree {
	vector<int> t;
	seg_tree() {
		t.resize(4 * maxn);
	}
	void init() {
		t.clear(); t.resize(4 * maxn);
	}
	void update(int pos, int val, int v = 1, int l = 1, int r = maxn - 1) {
		if (l == r) {
			t[v] += val;
			return;
		}
		int m = (l + r) / 2;
		if (pos <= m) update(pos, val, 2 * v, l, m);
		else update(pos, val, 2 * v + 1, m + 1, r);
		t[v] = t[2 * v] + t[2 * v + 1];
	}
	int get(int l, int r, int v = 1, int tl = 1, int tr = maxn - 1) {
		if (tl > r || tr < l) return 0;
		if (tl >= l && tr <= r) return t[v];
		int m = (tl + tr) / 2;
		return get(l, r, 2 * v, tl, m) + get(l, r, 2 * v + 1, m + 1, tr);
	}
} IT1;

struct persistent {
	vector<int> t, L, R;
	int num;
	persistent() {
		num = 0;
		t.resize(1e7);
		L.resize(1e7);
		R.resize(1e7);
	}
	int update(int pos, int val, int v, int l = 1, int r = maxn - 1) {
		if (pos < l || pos > r) return v;
		if (l == r) {
			t[++num] = t[v] + val;
			return num;
		}
		int m = (l + r) / 2, cur = ++num;
		L[cur] = update(pos, val, L[v], l, m);
		R[cur] = update(pos, val, R[v], m + 1, r);
		t[cur] = t[L[cur]] + t[R[cur]];
		return cur;
	}
	int get(int l, int r, int v, int tl = 1, int tr = maxn - 1) {
		if (tl > r || tr < l) return 0;
		if (tl >= l && tr <= r) return t[v];
		int m = (tl + tr) / 2;
		return get(l, r, L[v], tl, m) + get(l, r, R[v], m + 1, tr);
	}
} IT2;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i], idx[i] = i;
		vals.pb(a[i]); vals.pb(b[i]);
	}
	for (int i = 1; i <= k; i++) {
		cin >> q[i];
		vals.pb(q[i]);
	}
	sort(all(vals));
	vals.erase(unique(all(vals)), vals.end());
	for (int i = 1; i <= n; i++) {
		a[i] = lower_bound(all(vals), a[i]) - vals.begin() + 1;
		b[i] = lower_bound(all(vals), b[i]) - vals.begin() + 1;
	}
	for (int i = k; i >= 1; i--) {
		q[i] = lower_bound(all(vals), q[i]) - vals.begin() + 1;
		node[i] = IT2.update(q[i], 1, node[i + 1]);
	}
	// for (int i = 1; i <= n; i++)
		// clog << a[i] << ' ' << b[i] << endl;
	// for (int i = 1; i <= k; i++)
		// clog << q[i] << endl;
	for (int i = 1; i <= n; i++)
		L[i] = 1, R[i] = k;
	for (int t = 0; t < 18; t++) {
		for (int i = 1; i <= n; i++)
			que[(L[i] + R[i]) / 2].pb(i);
		IT1.init();
		for (int i = k; i >= 1; i--) {
			IT1.update(q[i], 1);
			// if (i == 3) clog << q[i] << ' ' << IT1.get(1, 1);
			for (int j : que[i])
				if (IT1.get(min(a[j], b[j]), max(a[j], b[j]) - 1)) {
					bst[j] = i;
					L[j] = i + 1;
				}
				else R[j] = i - 1;
			que[i].clear();
		}
	}
	long long res = 0;
	for (int i = 1; i <= n; i++) {
		int p = bst[i], lo = min(a[i], b[i]), hi = max(a[i], b[i]);
		int cnt = IT2.get(hi, SZ(vals), node[p + 1]);
		if (!p) res += (cnt & 1 ? vals[b[i] - 1] : vals[a[i] - 1]);
		else res += (cnt & 1 ? vals[lo - 1] : vals[hi - 1]);
	}
	cout << res;
}

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