Submission #1267485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267485		g4yuhg	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	377 ms	29516 KiB

fortune_telling2

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define pii pair<ll, ll> 
#define MP make_pair
#define fi first
#define se second
#define TASK "connect"
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 1000005
#define LOG 18
#define endl '\n'
using namespace std;

ll n, m, s, kq[N];
pii a[N];
pii t[N];
vector<ll> ns;

bool cmp(pii a, pii b) {
	return max(a.fi, a.se) > max(b.fi, b.se);
}

ll st[4 * N], bit[N];

void upd(ll u, ll v) {
	ll idx = u;
	while (idx <= s) {
		bit[idx] += v;
		idx += idx & (-idx);
	}
}

ll get(ll u) {
	ll idx = u, ans = 0;
	while (idx > 0) {
		ans += bit[idx];
		idx -= idx & (-idx);
	}
	return ans;
}

void update(ll id, ll l, ll r, ll i, ll v) {
	if (i > r || i < l) return;
	if (l == r) {
		if (v == 0) st[id] = 0;
		else st[id] = max(st[id], v);
		return;
	}
	ll mid = (l + r) / 2;
	update(id * 2, l, mid, i, v);
	update(id * 2 + 1, mid + 1, r, i, v);
	st[id] = max(st[id * 2], st[id * 2 + 1]);
}

ll get(ll id, ll l, ll r, ll L, ll R) {
	if (l > R || r < L) return 0;
	if (L <= l && r <= R) return st[id];
	ll mid = (l + r) / 2;
	return max(get(id * 2, l, mid, L, R), get(id * 2 + 1, mid + 1, r, L, R));
}

void pre() {
	s = ns.size();
	sort(ns.begin(), ns.end());
	ns.resize(unique(ns.begin(), ns.end()) - ns.begin());
	for (int i = 1; i <= n; i ++) {
		a[i].fi = lower_bound(ns.begin(), ns.end(), a[i].fi) - ns.begin() + 1;
		a[i].se = lower_bound(ns.begin(), ns.end(), a[i].se) - ns.begin() + 1;
	}
	for (int i = 1; i <= m; i ++) {
		t[i].fi = lower_bound(ns.begin(), ns.end(), t[i].fi) - ns.begin() + 1;
		update(1, 1, s, t[i].fi, i);
		//cout << " len " << t[i].fi << " " << i << endl;
		t[i].se = i;
	}
	sort(t + 1, t + 1 + m);
}

void solve() {
	ll ans = 0;
	ll cur = m;
	for (int i = 1; i <= n; i ++) {
		//cout << a[i].fi << " " << a[i].se << endl;
	}
	for (int i = 1; i <= m; i ++) {
		//cout << t[i].fi << " ";
	}
	//cout << endl;
	for (int i = 1; i <= n; i ++) {
		bool flag = 0;
		if (a[i].fi > a[i].se) {
			flag = 1;
			swap(a[i].fi, a[i].se);
		}
		while (cur >= 1 && t[cur].fi >= max(a[i].fi, a[i].se)) {
			update(1, 1, s, t[cur].fi, 0);
			//cout << " t cur ve 0 " << t[cur].fi << " " << st[1] << endl;
			upd(t[cur].se, 1);
			//cout << "upd cur " << t[cur].se << endl;
			cur -- ;
		}
		if (a[i].fi == a[i].se) {
			ans += ns[a[i].fi - 1];
			continue;
		}
		ll id = get(1, 1, s, a[i].fi, a[i].se - 1);
		ll dem = get(s) - get(id);
		//cout << i << " id " << id << " flag " << flag << " d " << dem << " a " << ans << endl;
		if (id == 0 && flag == 1) {
			dem ++ ;
			if (dem % 2 == 1) {
				ans += ns[a[i].se - 1];
			}
			else {
				ans += ns[a[i].fi - 1];
			}
			continue;
		}
		if (a[i].fi < a[i].se && id > 0) swap(a[i].fi, a[i].se);
		//cout << "_ " << a[i].fi << " " << a[i].se << endl;
		if (dem % 2 == 0) {
			ans += ns[a[i].fi - 1];
		}
		else {
			ans += ns[a[i].se - 1];
		}
	}
	cout << ans;
}

signed main(void) {
	faster;
	
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i].fi >> a[i].se;
		ns.push_back(a[i].fi);
		ns.push_back(a[i].se);
	}
	sort(a + 1, a + 1 + n, cmp);
	
	for (int i = 1; i <= m; i ++) {
		cin >> t[i].fi;
		ns.push_back(t[i].fi);
	}
	
	pre();
	solve();
	
	return 0;
}

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