Submission #706671

#	Time	Username	Problem	Language	Result	Execution time	Memory
706671		Makarooni	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	561 ms	83216 KiB

fortune_telling2

/* IN THE NAME OF GOD */
/* |\/| /-\ |\| | |\/| /-\ */

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

#define sz(x) (int)x.size()
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define mr make_pair
//#define int long long
#define pii pair<int, int>
typedef long double ld;
typedef long long ll;

mt19937 rng (chrono::high_resolution_clock::now().time_since_epoch().count());

const int N = 1e6 + 10;
const int MOD = 1e9 + 7;
const int inf = 1e9 + 1;

int a[N], b[N], x[N], seg[N * 4], wh[N * 4], fen[N], lst[N];
vector<int> vec, V[N];
vector<pii> t[N];

void bulid(int id, int s, int e){
	if(s == e){
		if(t[s].empty())
			seg[id] = -1;
		else{
			seg[id] = t[s].back().F;
			wh[id] = t[s].back().S;
			t[s].pop_back();
		}
		return;
	}
	int mid = (s + e) / 2;
	bulid(id * 2, s, mid);
	bulid(id * 2 + 1, mid + 1, e);
	if(seg[id * 2] > seg[id * 2 + 1]){
		seg[id] = seg[id * 2];
		wh[id] = wh[id * 2];
	}
	else{
		seg[id] = seg[id * 2 + 1];
		wh[id] = wh[id * 2 + 1];
	}
}

void upd(int id, int s, int e, int p){
	if(s > p || p > e)
		return;
	if(s == e){
		if(t[s].empty())
			seg[id] = -1;
		else{
			seg[id] = t[s].back().F;
			wh[id] = t[s].back().S;
			t[s].pop_back();
		}
		return;
	}
	int mid = (s + e) / 2;
	upd(id * 2, s, mid, p);
	upd(id * 2 + 1, mid + 1, e, p);
	if(seg[id * 2] > seg[id * 2 + 1]){
		seg[id] = seg[id * 2];
		wh[id] = wh[id * 2];
	}
	else{
		seg[id] = seg[id * 2 + 1];
		wh[id] = wh[id * 2 + 1];
	}
}

pii get(int id, int s, int e, int l, int r){
	if(s > r || e < l)
		return mr(-1, -1);
	if(l <= s && e <= r)
		return mr(seg[id], wh[id]);
	int mid = (s + e) / 2;
	pii p = get(id * 2, s, mid, l, r), q = get(id * 2 + 1, mid + 1, e, l, r);
	return max(p, q);
}

void add(int p, int x){
	for(; p < N; p += p & -p)
		fen[p] += x;
}

int fget(int p){
	int ret = 0;
	for(; p > 0; p -= p & -p)
		ret += fen[p];
	return ret;
}

int f(int x){
	return lower_bound(all(vec), x) - vec.begin() + 1;
}

int32_t main(){
	ios_base:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, k;
	cin >> n >> k;
	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i];
		vec.pb(a[i]);
		vec.pb(b[i]);
	}
	for(int i = 1; i <= k; i++){
		cin >> x[i];
		vec.pb(x[i]);
	}
	sort(all(vec));
	vec.resize(unique(all(vec)) - vec.begin());
	for(int i = 1; i <= n; i++)
		t[f(min(a[i], b[i]))].pb(mr(max(a[i], b[i]), i));
	for(int i = 1; i < N; i++)
		sort(all(t[i]));
	bulid(1, 1, N - 1);
	for(int i = k; i >= 1; i--){
		while(1){
			pii p = get(1, 1, N - 1, 1, f(x[i]));
			if(p.F <= x[i])
				break;
			lst[p.S] = i;
			upd(1, 1, N - 1, f(min(a[p.S], b[p.S])));
		}
	}
	for(int i = 1; i <= n; i++)
		V[lst[i]].pb(i);
	ll ans = 0;
	for(int i = k; i >= 0; i--){
		if(i != 0){
			add(1, 1);
			add(f(x[i]) + 1, -1);
		}
		for(int v : V[i]){
			int r = fget(f(max(b[v], a[v])));
			if(i == 0){
				if(r % 2)
					ans += b[v];
				else
					ans += a[v];
			}
			else if(a[v] < b[v]){
				if(r % 2)
					ans += a[v];
				else
					ans += b[v];
			}
			else{
				if(r % 2)
					ans += b[v];
				else
					ans += a[v];
			}
		}
	}
	cout << ans;
}

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