oj.uz

답안 #705611

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
705611 2023-03-04T19:28:11 Z Asymmetry Examination (JOI19_examination) C++17
0 / 100
 3000 ms 11612 KB 
#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) {
		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 (S[i] + T[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
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 33 ms 872 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3078 ms 11612 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3078 ms 11612 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 33 ms 872 KB Output isn't correct
8 Halted 0 ms 0 KB -