Submission #705621

#	Time	Username	Problem	Language	Result	Execution time	Memory
705621		Asymmetry	Examination (JOI19_examination)	C++17	2 / 100	3070 ms	9372 KiB

examination

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<'\n';}(x)
#else
#define debug(...) {}
#endif

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, q;
	cin >> n >> q;
	vector S(n, 0), T(n, 0), K(n, 0);
	vector<int> values;
	REP (i, n) {
		cin >> S[i] >> T[i];
		values.emplace_back(S[i]);
		values.emplace_back(T[i]);
		K[i] = S[i] + T[i];
		values.emplace_back(K[i]);
	}
	vector<tuple<int, int, int>> queries(q);
	for (auto &[a, b, c] : queries) {
		cin >> a >> b >> c;
		values.emplace_back(a);
		values.emplace_back(b);
		values.emplace_back(c);
	}
	sort(values.begin(), values.end());
	values.erase(unique(values.begin(), values.end()), values.end());

	auto scale = [&](int x) {
		return (int)(lower_bound(values.begin(), values.end(), x) - values.begin());
	};

	for (int &i : S)
		i = scale(i);
	for (int &i : T)
		i = scale(i);
	for (int &i : K)
		i = scale(i);
	for (auto &[a, b, c] : queries) {
		a = scale(a);
		b = scale(b);
		c = scale(c);
		debug(a, b, c);
	}
	debug(S);
	debug(T);
	debug(K);

	vector<int> ans(q);
	auto merge = [&](vector<int> point_id, vector<int> query_id) {
		sort(point_id.begin(), point_id.end(), [&](int x, int y) {
				return S[x] < S[y];});
		sort(query_id.begin(), query_id.end(), [&](int x, int y) {
				return get<0>(queries[x]) < get<0>(queries[y]);});
		debug(point_id);
		debug(query_id);
		for (int i : point_id) {
			for (int j : query_id) {
				auto [a, b, c] = queries[j];
				debug(j, i, S[i], a, T[i], b, K[i], c, (S[i] >= a && T[i] >= b && K[i] >= c));
				ans[j] += (S[i] >= a && T[i] >= b && K[i] >= c);
			}
		}
	};

	function<void(int, int, vector<int>, vector<int>)> rek =
		[&](int lf, int rg, vector<int> point_id, vector<int> query_id) {
		debug(lf, rg, point_id, query_id);
		if (lf == rg) {
			merge(point_id, query_id);
			return;
		}
		int mid = (lf + rg) / 2;
		debug(mid);
		vector<int> left_point_id, right_point_id, left_query_id, right_query_id;
		for (int i : point_id) {
			if (K[i] <= mid)
				left_point_id.emplace_back(i);
			else
				right_point_id.emplace_back(i);
		}
		for (int i : query_id) {
			if (get<2>(queries[i]) <= mid)
				left_query_id.emplace_back(i);
			else
				right_query_id.emplace_back(i);
		}

		merge(right_point_id, left_query_id);

		rek(lf, mid, left_point_id, left_query_id);
		rek(mid + 1, rg, right_point_id, right_query_id);
	};
	vector<int> point_id(n), query_id(q);
	iota(point_id.begin(), point_id.end(), 0);
	iota(query_id.begin(), query_id.end(), 0);
	rek(0, ssize(values) - 1, point_id, query_id);
	//merge(point_id, query_id);

	REP (i, q)
		cout << ans[i] << '\n';
}

• Subtask 1: 2 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57