Submission #845983

#	Time	Username	Problem	Language	Result	Execution time	Memory
845983		LeonaRaging	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	22 ms	127836 KiB

fortune_telling2

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

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

const int maxn = 1e5 + 4;

int n, k, a[maxn], b[maxn], q[maxn], idx[maxn], node[maxn];
vector<int> vals, que[3 * maxn];

struct seg_tree {
	vector<int> t;
	seg_tree() {
		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 walk(int v = 1, int l = 1, int r = maxn - 1) {
		if (l == r) return l;
		int m = (l + r) / 2;
		if (t[2 * v + 1]) return walk(2 * v + 1, m + 1, r);
		return walk(2 * v, l, m);
	}
} 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;
		que[q[i]].pb(i);
		node[i] = IT2.update(q[i], 1, node[i + 1]);
	}
	sort(idx + 1, idx + 1 + n, [&](int i, int j) {
		return min(a[i], b[i]) > min(a[j], b[j]);
	});
	// for (int i = 1; i <= n; i++)
		// clog << a[i] << ' ' << b[i] << endl;
	// for (int i = 1; i <= k; i++)
		// clog << q[i] << endl;
	int pos = SZ(vals);
	long long res = 0;
	for (int i = 1; i <= n; i++) {
		int lo = min(a[i], b[i]), hi = max(a[i], b[i]);
		while (pos > lo) {
			for (int i : que[pos])
				IT1.update(i, 1);
			pos--;	
		}
		int p = IT1.walk();
		res += (IT2.get(hi, SZ(vals), node[p]) & 1 ? vals[lo - 1] : vals[hi - 1]);
	}
	cout << res;
}

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