Submission #39459

#	Time	Username	Problem	Language	Result	Execution time	Memory
39459		Noam527	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	316 ms	262144 KiB

fortune_telling2

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <time.h>
#include <stack>
#include <queue>
#include <random>
#include <fstream>
#define endl '\n'
#define flush fflush(stdout), cout.flush()
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define debug cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll hs = 199;
const ldb eps = 1e-9, pi = acos(-1);
using namespace std;

const int maxn = 200002;

struct wavelet {
	int lo, hi;
	vector<int> pr;
	wavelet *l = 0, *r = 0;
	wavelet(int *le, int *ri, int x, int y) {
		lo = x, hi = y;
		if (le < ri && lo < hi) {
			int mid = lo + (hi - lo) / 2;
			auto f = [&mid](int x) {
				return x <= mid;
			};
			pr.reserve(ri - le + 1);
			pr.push_back(0);
			for (int *i = le; i != ri; i++)
				pr.push_back(pr.back() + f(*i));
			int *piv = stable_partition(le, ri, f);
			l = new wavelet(le, piv, x, mid), r = new wavelet(piv, ri, mid + 1, y);
		}
	}
	// count greater/equals than k in [l, r]
	int cge(int l, int r, int k) {
		if (l > r || hi < k) return 0;
		if (lo >= k) return r - l + 1;
		int le = pr[l - 1], ri = pr[r];
		return this->l->cge(le + 1, ri, k) + this->r->cge(l - le, r - ri, k);
	}
};
struct sparse {
	int sp[19][maxn];
	sparse(int x[maxn]) {
		for (int i = 0; i < maxn; i++) sp[0][i] = x[i];
		for (int i = 1, l = 2; l <= maxn; i++, l <<= 1)
			for (int j = 0; j + l <= maxn; j++)
				sp[i][j] = max(sp[i - 1][j], sp[i - 1][j + l / 2]);
	}
	int clz(int x) {
		static int lo, hi, mid;
		lo = 0, hi = 30;
		while (lo < hi) {
			mid = (lo + hi + 1) >> 1;
			if (x >> mid) lo = mid;
			else hi = mid - 1;
		}
		return lo;
	}
	int query(int l, int r) {
		static int c;
		c = clz(r - l + 1);
		return max(sp[c][l], sp[c][r - (1 << c) + 1]);
	}
};

int n, k, a[2][maxn], b[maxn], c[maxn];
ll ans = 0;

bool cmp(const int &x, const int &y) {
	return b[x] < b[y];
}

int lowerbound(const int &x) {
	static int lo, hi, mid;
	lo = 0, hi = n - 1;
	while (lo < hi) {
		mid = (lo + hi) >> 1;
		if (b[c[mid]] < x) lo = mid + 1;
		else hi = mid;
	}
	if (b[c[lo]] < x) lo++;
	return lo;
}

int main() {
	fast;
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> a[0][i] >> a[1][i];
	for (int i = 0; i < k; i++) cin >> b[i];
	wavelet w = wavelet(b, b + k, 1, 1e9);
	for (int i = 0; i < n; i++) c[i] = i;
	sort(c, c + n, cmp);
	sparse sp = sparse(c);
	
	for (int i = 0, mn, mx, lo, hi; i < n; i++) {
		mn = min(a[0][i], a[1][i]);
		mx = max(a[0][i], a[1][i]);
		lo = lowerbound(mn), hi = lowerbound(mx) - 1;
		if (lo > hi)
			ans += a[w.cge(1, k, mx) & 1][i];
		else
			ans += a[w.cge(sp.query(lo, hi), k, mx) & 1][i];
		
		
	}
	cout << ans << endl;
}

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