oj.uz

Submission #705621

# Submission time Handle Problem Language Result Execution time Memory
705621 2023-03-04T19:57:15 Z Asymmetry Examination (JOI19_examination) C++17
2 / 100
 3000 ms 9372 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) {
		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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 30 ms 752 KB Output is correct
8 Correct 28 ms 836 KB Output is correct
9 Correct 29 ms 832 KB Output is correct
10 Correct 28 ms 724 KB Output is correct
11 Correct 26 ms 724 KB Output is correct
12 Correct 22 ms 640 KB Output is correct
13 Correct 48 ms 984 KB Output is correct
14 Correct 50 ms 960 KB Output is correct
15 Correct 47 ms 972 KB Output is correct
16 Correct 41 ms 912 KB Output is correct
17 Correct 24 ms 724 KB Output is correct
18 Correct 9 ms 676 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3070 ms 9372 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3070 ms 9372 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 30 ms 752 KB Output is correct
8 Correct 28 ms 836 KB Output is correct
9 Correct 29 ms 832 KB Output is correct
10 Correct 28 ms 724 KB Output is correct
11 Correct 26 ms 724 KB Output is correct
12 Correct 22 ms 640 KB Output is correct
13 Correct 48 ms 984 KB Output is correct
14 Correct 50 ms 960 KB Output is correct
15 Correct 47 ms 972 KB Output is correct
16 Correct 41 ms 912 KB Output is correct
17 Correct 24 ms 724 KB Output is correct
18 Correct 9 ms 676 KB Output is correct
19 Execution timed out 3070 ms 9372 KB Time limit exceeded
20 Halted 0 ms 0 KB -