Submission #705627

#	Time	Username	Problem	Language	Result	Execution time	Memory
705627		Asymmetry	Examination (JOI19_examination)	C++17	100 / 100	594 ms	31192 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

/*
 * Opis: Drzewo potęgowe
 * Czas: O(\log n)
 * Użycie:
 *   wszystko indexowane od 0
 *   update(pos, val) dodaje val do elementu pos
 *   query(pos) zwraca sumę na przedziale [0, pos]
 */

struct Fenwick {
	vector<int> s;
	Fenwick(int n) : s(n) {}
	void update(int pos, int val) {
		for(; pos < ssize(s); pos |= pos + 1)
			s[pos] += val;
	}
	int query(int pos) {
		int ret = 0;
		for(pos++; pos > 0; pos &= pos - 1)
			ret += s[pos - 1];
		return ret;
	}
	int query(int l, int r) {
		return query(r) - query(l - 1);
	}
};

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<int> X(q), Y(q), Z(q);
	REP (i, q) {
		cin >> X[i] >> Y[i] >> Z[i];
		values.emplace_back(X[i]);
		values.emplace_back(Y[i]);
		values.emplace_back(Z[i]);
	}
	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 (int &i : X)
		i = scale(i);
	for (int &i : Y)
		i = scale(i);
	for (int &i : Z)
		i = scale(i);
	debug(S);
	debug(T);
	debug(K);
	debug(X);
	debug(Y);
	debug(Z);

	Fenwick tree(ssize(values));
	vector<int> ans(q);
	auto merge = [&](vector<int> point_id, vector<int> query_id) {
		vector<tuple<int, int, int>> sr;
		for (int id : point_id)
			sr.emplace_back(-S[id], 0, id);
		for (int id : query_id)
			sr.emplace_back(-X[id], 1, id);
		sort(sr.begin(), sr.end());
		for (auto [val, type, id] : sr) {
			if (type)
				ans[id] += tree.query(Y[id], ssize(values) - 1);
			else
				tree.update(T[id], 1);
		}
		for (int id : point_id)
			tree.update(T[id], -1);
	};

	function<void(int, int, vector<int>, vector<int>)> rek =
		[&](int lf, int rg, vector<int> point_id, vector<int> query_id) {
		if (lf == rg) {
			merge(point_id, query_id);
			return;
		}
		int mid = (lf + rg) / 2;
		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 (Z[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);

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

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