Submission #1125312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125312		nuutsnoynton	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	2045 ms	158064 KiB

fortune_telling2

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair < ll, ll>;
const ll N = 4e5 + 2;

struct S {
	ll mx_ind, mx_val;
};
struct qr{
	ll ans_ind, ind, val;
};
ll c[N], Q[N];
S ST[16 * N];
ll TR[16 * N];
void Build(ll p, ll lo, ll hi) {
	if ( lo == hi) {
		ST[p].mx_ind = lo;
		ST[p].mx_val = c[lo];
		return ;
	}
	ll mid = (lo + hi)/2;
	Build(2 * p, lo, mid);
	Build(2 * p + 1, mid + 1, hi);
	if(ST[2 * p].mx_val > ST[2 * p + 1].mx_val) ST[p] = ST[2 *p];
	else ST[p] = ST[2 * p + 1];
}
ll Find(ll p, ll lo, ll hi, ll l, ll r) {
	if ( lo > r || l > hi) return 0;
	if ( l <= lo && hi <= r) {
		return ST[p].mx_val;
	}
	ll mid = (lo + hi)/2;
	return max(Find(2 * p, lo, mid, l, r), Find(2 * p + 1, mid + 1, hi, l, r));
}
void Update(ll p, ll lo, ll hi, ll x, ll y) {
	if (lo == hi) {
		TR[p] += y;
		return ;
	}
	ll mid = (lo + hi)/2;
	if ( x <= mid) Update(2 * p, lo, mid, x, y);
	else Update(2 * p + 1, mid + 1, hi, x, y);
	TR[p] = TR[2 * p] + TR[2 * p + 1];
}
ll Sum(ll p, ll lo, ll hi, ll l,ll r) {
	if ( lo > r || l > hi) return 0;
	if ( l <= lo && hi <= r) {
		return TR[p];
	}
	ll mid = (lo + hi)/2;
	return Sum(2 * p, lo, mid, l, r) + Sum(2 * p + 1, mid + 1, hi, l, r);
}
bool cmp(qr A, qr B) {
	return A.ind < B.ind;
}
map < ll, ll > mp, to, beck;
int main() {
	ll n, q, i, x, ind, p, y, lo, hi;
	
	cin >> n >> q;
	
	ll a[n + 2], b[n + 2];
	for (i =1; i <= n; i ++) {
		cin>> a[i] >> b[i];
		mp[a[i]] ++;
		mp[b[i]] ++;
	}
	vector < pair < ll , ll > > v;
	for (i = 1; i <= q; i ++) {
		cin >> Q[i];
		mp[Q[i]] ++;
	}
	ind = 1;
	for ( auto R : mp) {
		to[R.first] = ind;
		beck[ind] = R.first;
		ind ++;
	}
	for (i = 1; i <= n; i ++) a[i] = to[a[i]], b[i] = to[b[i]];
	for (i = 1; i <= q; i ++) Q[i] = to[Q[i]];
	for (i =1; i <= q; i ++) {
		v.push_back({Q[i], i});
	}
	sort(v.begin(), v.end());
	for (i = 1; i <= q; i ++) {
		c[i] = v[i - 1].second;
	}
	
	Build(1, 1, q);
	vector < qr > queries;
	for (i = 1; i <= n; i ++) {
		x = a[i];
		y = b[i];
		if ( x > y) swap(x, y);
		lo = lower_bound(v.begin(), v.end(), make_pair(x , 0ll)) - v.begin();
		hi = lower_bound(v.begin(), v.end(), make_pair(y, 0ll)) - v.begin();
		hi ++;
		lo ++;
		hi --;
		p = 1;
		if ( lo <= hi) {
			p= Find(1, 1, q, lo, hi);
			a[i] = y;
			b[i] = x;
		}
		
		queries.push_back({i, p, y});
	}
	ll ans[N];
	sort(queries.begin(), queries.end(), cmp);
	for (i = q ; i >= 1;i --) {
		Update(1, 1, 6e5, Q[i], 1);
		while(!queries.empty() && queries.back().ind == i) {
			p = Sum(1, 1, 6e5, queries.back().val, 6e5);
			ans[queries.back().ans_ind] = p;
			queries.pop_back();
		}
	}
	ll ans_sum = 0;
	for (i = 1; i <= n; i ++) {
		if ( ans[i] % 2 == 1) ans_sum += beck[b[i]];
		else ans_sum += beck[a[i]];
	}
	cout << ans_sum << endl;
}

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