Submission #975543

#	Time	Username	Problem	Language	Result	Execution time	Memory
975543		falaz	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	301 ms	113852 KiB

fortune_telling2

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

#define int long long
//#define endl '\n'

#define F first
#define S second

#define SZ(a) int32_t(a.size())

namespace RMQ {
	const int N = 6e5 + 7, LG = 20;
	int rmq[LG][N];
	void add(int i, int k) {
		rmq[0][i] = k;
		return;
	}
	void pre(int n) {
		for (int i = 0; i < LG - 1; ++i)
			for (int j = 0; j + (2 << i) <= n; ++j)
				rmq[i + 1][j] = max(rmq[i][j], rmq[i][j + (1 << i)]);
		return;
	}
	int get(int l, int r) {
		int L = __lg(r - l);	
		return max(rmq[L][l], rmq[L][r - (1 << L)]);
	}
}

namespace FEN {
	const int N = 6e5 + 7;
	bitset<N> fen;
	bool f;
	void add(int i) {
		f = !f;
		i++;
		for (; i < N; i += (i & -i))
			fen[i] = !fen[i];
		return;
	}
	bool get(int i) {
		i++;
		bool ret = 0;
		for (; i; i -= (i & -i)) {
			ret ^= fen[i];
		}
		return ret;
	}
	bool gets(int i) {
		return f ^ get(i - 1);
	}

}

const int N = 6e5 + 7;

struct rmp {
	int mn, mx;
}mp[N];

int n, q, a[N], b[N], t[N], ans;
pair<int, int> f[N];
vector<int> com, sv1[N];
vector<pair<int, int>> sv2;

void ip() {
	cin >> n >> q;
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
		mp[i].mn = min(a[i], b[i]);
		mp[i].mx = max(a[i], b[i]);
		com.push_back(a[i]);
		com.push_back(b[i]);
	}
	for (int i = 0; i < q; ++i) {
		cin >> t[i];
		com.push_back(t[i]);
	}
	return;
}

void compres() {
	sort(com.begin(), com.end());
	com.resize(unique(com.begin(), com.end()) - com.begin());

	for (int i = 0; i < n; i++)
		a[i] = lower_bound(com.begin(), com.end(), a[i]) - com.begin(),
		b[i] = lower_bound(com.begin(), com.end(), b[i]) - com.begin();
	for (int i = 0; i < q; i++)
		t[i] = lower_bound(com.begin(), com.end(), t[i]) - com.begin();
	return;
}

void pre() {
	for (int i = 0; i < q; ++i)
		f[i] = {t[i], i};
	sort(f, f + q);
	for (int i = 0; i < q; ++i)
		RMQ::add(i, f[i].S);
	RMQ::pre(q);
	return;
}

void solve() {
	for (int i = 0; i < n; ++i) {
		int mn = min(a[i], b[i]), mx = max(a[i], b[i]), l;
		pair<int, int> a1 = {mn, -1}, b1 = {mx, -1};
		int bsn = lower_bound(f, f + q, a1) - f;
		int bsx = upper_bound(f, f + q, b1) - f;
		(bsn >= bsx) ? l = - 1 : l = RMQ::get(bsn, bsx);
	//	cout << mn << " " << mx << " " << bsn << " " << bsx << " " << l << endl;
		bool pb = (a[i] <= b[i]);
		(l == -1) ? sv2.push_back({pb , i}) : sv1[l].push_back(i);
	}
	for (int i = q - 1;  ~i; --i) {
	//	cout << "gg" << i << " " << sv1[i].size() << endl;
		for (auto j : sv1[i]) {
			int l = 0;
			int mx = max(a[j], b[j]);
			l ^= FEN::gets(mx);
			ans += (l ? mp[j].mn : mp[j].mx);
		}
		FEN::add(t[i]);
	}

	for (auto i: sv2) {
		int l = i.F;
		int mx = max(a[i.S], b[i.S]);
		l ^= FEN::gets(mx);
		ans += (l ? mp[i.S].mn : mp[i.S].mx);
	}
	return;
}

void op() {
	cout << ans;
	return;
}

void run() {
	ip();
	compres();
	pre();
	solve();
	op();
	return;
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	run();

	return 0;
}

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