제출 #1288363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288363		pasta	운세 보기 2 (JOI14_fortune_telling2)	C++20	35 / 100	749 ms	81144 KiB

fortune_telling2

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

//#define int                         long long

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define S  second
#define F  first
#define all(x)		(x).begin(),(x).end()
#define migmig       ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


#define lc							id << 1
#define rc							lc|1
#define mid							((l + r)/2)

const int maxn = 3e5 + 10;
//const int maxk = 101;
const int mod = 998244353;
const int inf = 1e9 + 1;
const int LOG = 21;

int n, k, a[maxn], b[maxn], t[maxn], f[maxn], mx[maxn * 4];
map<int, int> lst;
vector<int> kl, seg[maxn * 4];

void build_f(int id = 1, int l = 0, int r = kl.size()) {
	if (l + 1 == r) {
		mx[id] = lst[kl[l]];
		return;
	}
	build_f(lc, l, mid);
	build_f(rc, mid, r);
	mx[id] = max(mx[lc], mx[rc]);
}

int get_mx(int ql, int qr, int id = 1, int l = 0, int r = kl.size()) {
//	if (l == r)
//		return 0;
	if (r <= ql || qr <= l)
		return 0;
	if (ql <= l && r <= qr)
		return mx[id];
	return max(get_mx(ql, qr, lc, l, mid), get_mx(ql, qr, rc, mid, r));
}

vector<int> merge(vector<int> A, vector<int> B) {
	vector<int> ret;
	int i = 0, j = 0;
	while (i < A.size() && j < B.size()) {
		if (A[i] <= B[j]) {
			ret.pb(A[i]);
			i++;
		}
		else {
			ret.pb(B[j]);
			j++;
		}
	}
	
	while (i < A.size()) {
		ret.pb(A[i]);
		i++;
	}
	
	while (j < B.size()) {
		ret.pb(B[j]);
		j++;
	}
	
	return ret;
}


void build(int id = 1, int l = 1, int r = k + 1) {
	if (l + 1 == r) {
		seg[id].pb(t[l]);
		return;
	}
	build(lc, l, mid);
	build(rc, mid, r);
	seg[id] = merge(seg[lc], seg[rc]);
}


int get(int ql, int qr, int x, int id = 1, int l = 1, int r = k + 1) {
	if (r <= ql || qr <= l)
		return 0;
	if (ql <= l && r <= qr) {
		int cnt = lower_bound(all(seg[id]), x - 1) - seg[id].begin();
		return (seg[id].size() - cnt);
	}
	return (get(ql, qr, x, lc, l, mid) + get(ql, qr, x, rc, mid, r));
}

signed main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
		lst[a[i]] = 0;
		lst[b[i]] = 0;
		kl.pb(a[i]);
		kl.pb(b[i]);
	}
	for (int i = 1; i <= k; i++) {
		cin >> t[i];
		lst[t[i]] = i;
		kl.pb(t[i]);
	}
	
	sort(all(kl));
	kl.erase(unique(all(kl)), kl.end());
//	for (int x : kl)
//		cout << x << ' ';
//	cout << '\n';
	build_f();
	for (int i = 1; i <= n; i++) {
		int l = lower_bound(all(kl), a[i]) - kl.begin();
		int r = lower_bound(all(kl), b[i]) - kl.begin();
		if (l > r)
			swap(l, r);
		f[i] = get_mx(l, r);
//		cout << i << ' ' << f[i] << '\n';
	}
	build();
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		int cnt = get(f[i] + 1, k + 1, max(a[i], b[i]));
		if (f[i] != 0) {
			if (a[i] > b[i])
				swap(a[i], b[i]);
			if (cnt % 2 == 0)
				ans += b[i];
			else
				ans += a[i];
		}
		else {
			if (cnt % 2 == 0)
				ans += a[i];
			else
				ans += b[i];
		}
	}
	cout << ans << '\n';
}

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