Submission #471697

#	Time	Username	Problem	Language	Result	Execution time	Memory
471697		prvocislo	Examination (JOI19_examination)	C++17	100 / 100	612 ms	16172 KiB

examination

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
typedef long long ll;
using namespace std;

const int maxn = 1e5 + 5;
struct ev { int a, b, c, qu, i; };
bool cmpa(const ev& a, const ev& b) { return a.a == b.a ? a.qu > b.qu : a.a < b.a; }
bool cmpb(const ev& a, const ev& b) { return a.b == b.b ? a.qu > b.qu : a.b < b.b; }
int ans[maxn];
void solve_bc(const vector<ev>& v, int l, int r)
{
	if (l >= r) return;
	int m = (l + r) / 2;
	vector<int> c;
	for (int i = m + 1; i <= r; i++)
		if (!v[i].qu) c.push_back(v[i].c);
	sort(c.begin(), c.end());
	for (int i = l; i <= m; i++)
		if (v[i].qu) ans[v[i].i] += c.end() - lower_bound(c.begin(), c.end(), v[i].c);
	solve_bc(v, l, m);
	solve_bc(v, m + 1, r);
}
void solve_abc(const vector<ev>& v, int l, int r)
{
	if (l >= r) return;
	int m = (l + r) / 2;
	vector<ev> e;
	for (int i = l; i <= m; i++) if (v[i].qu)
		e.push_back(v[i]);
	for (int i = m + 1; i <= r; i++) if (!v[i].qu)
		e.push_back(v[i]);
	sort(e.begin(), e.end(), cmpb);
	solve_bc(e, 0, e.size() - 1);
	solve_abc(v, l, m);
	solve_abc(v, m + 1, r);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	vector<ev> e(n + q);
	for (int i = 0; i < n; i++) cin >> e[i].a >> e[i].b, e[i].c = e[i].a + e[i].b, e[i].qu = 0;
	for (int i = 0; i < q; i++) cin >> e[i + n].a >> e[i + n].b >> e[i + n].c, e[i + n].i = i, e[i + n].qu = 1;
	sort(e.begin(), e.end(), cmpa);
	solve_abc(e, 0, e.size() - 1);
	for (int i = 0; i < q; i++) cout << ans[i] << "\n";
	return 0;
}

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