Submission #317602

#	Time	Username	Problem	Language	Result	Execution time	Memory
317602		jungsnow	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	328 ms	52708 KiB

fortune_telling2

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second

using namespace std;
using ll = long long;

typedef pair<int, int> ii;

const int N = 200100;

int n, k, a[N], b[N];
int Log[N], rmq[N][20];
int bit[N], ans[N];
vector <ii> vec, g[N];

void upd(int idx, int val) {
	for (; idx; idx -= idx & -idx) {
		bit[idx] += val;
	}
}

int get(int idx) {
	int re = 0;
	for (; idx <= k; idx += idx & -idx) {
		re += bit[idx];
	}
	return re;
}

int get(int l, int r) {
	int _lg = Log[r - l + 1];
	return max(rmq[l][_lg], rmq[r - (1 << _lg) + 1][_lg]);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i] >> b[i];
	}
	for (int x, i = 1; i <= k; ++i) {
		cin >> x;
		vec.push_back(ii(x, i));
	}
	
	Log[0] = Log[1] = 0;
	for (int i = 2; i <= k; ++i) Log[i] = Log[i / 2] + 1;
	
	sort(vec.begin(), vec.end());
	for (int i = 0; i < k; ++i) rmq[i][0] = vec[i].y;
	for (int j = 1; j < 20; ++j) {
		for (int i = 0; i + (1 << j) <= k; ++i) {
			rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << j - 1)][j - 1]);
		}
	}
	
	for (int i = 1; i <= n; ++i) {
		int lb = min(a[i], b[i]), rb = max(a[i], b[i]);
		int l = lower_bound(vec.begin(), vec.end(), ii(lb, -1)) - vec.begin();
		int r = lower_bound(vec.begin(), vec.end(), ii(rb, -1)) - vec.begin() - 1;
		int pos = 0;
		if (l <= r) {
			pos = get(l, r);
			if (a[i] < b[i]) swap(a[i], b[i]);
		}
		g[r + 1].push_back(ii(i, pos + 1));	
	}
	
	for (int i = k - 1; i >= 0; --i) {
		upd(vec[i].y, 1);
		for (ii e : g[i]) ans[e.x] = get(e.y) & 1;
	}
	
	ll sum = 0;
	for (int i = 1; i <= n; ++i) {
		sum += ans[i] ? b[i] : a[i];
		//cerr << i << ' ' << ans[i] << '\n';
	}
	cout << sum << '\n';
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:56:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   56 |    rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << j - 1)][j - 1]);
      |                                                 ~~^~~

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