Submission #1265797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265797		canhnam357	Examination (JOI19_examination)	C++20	100 / 100	504 ms	83956 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define MASK(i) (1LL << (i))
#define int long long
const int inf = 2e9;
const int mod = 1e9 + 7;
const int N = 1000;
const int b = 1500;
void ckmax(int& f, int s)
{
	f = (f > s ? f : s);
}
void ckmin(int& f, int s)
{
	f = (f < s ? f : s);
}
const int MAXN = 4e5 + 5;
vector<int> nodes[MAXN], f[MAXN];
void fakeUpdate(int u, int v) {
	for (int x = u; x < MAXN; x += x & -x)
		nodes[x].push_back(v);
}

void fakeGet(int u, int v) {
	for (int x = u; x > 0; x -= x & -x)
		nodes[x].push_back(v);
}
void update(int u, int v) {
	for (int x = u; x < MAXN; x += x & -x)
		for (int y = lower_bound(nodes[x].begin(), nodes[x].end(), v) - nodes[x].begin() + 1; y <= nodes[x].size(); y += y & -y)
			f[x][y]++;
}

int get(int u, int v) {
	int res = 0;
	for (int x = u; x > 0; x -= x & -x)
		for (int y = upper_bound(nodes[x].begin(), nodes[x].end(), v) - nodes[x].begin(); y > 0; y -= y & -y)
			res += f[x][y];
	return res;
}
void solve()
{
	int n, nq;
	cin >> n >> nq;
	vector<tuple<int, int, int>> a(n);
	vector<int> cc;
	for (auto &[f, s, k] : a)
	{
		cin >> f >> s;
		k = f + s;
		f = -f, s = -s;
		cc.push_back(f);
		cc.push_back(s);
	}
	vector<tuple<int, int, int>> q(nq);
	for (auto &[x, y, z] : q)
	{
		cin >> x >> y >> z;
		x = -x, y = -y;
		cc.push_back(x);
		cc.push_back(y);
	}
	sort(all(cc));
	cc.erase(unique(all(cc)), cc.end());
	auto get_pos = [&](int val)
	{
		return upper_bound(all(cc), val) - cc.begin();
	};
	for (auto &[f, s, k] : a)
	{
		f = get_pos(f);
		s = get_pos(s);
		fakeUpdate(f, s);
	}
	for (auto &[x, y, z] : q)
	{
		x = get_pos(x);
		y = get_pos(y);
		fakeGet(x, y);
	}
	for (int i = 1; i < MAXN; i++)
	{
		if (nodes[i].empty()) continue;
		sort(nodes[i].begin(), nodes[i].end());
		nodes[i].erase(unique(nodes[i].begin(), nodes[i].end()), nodes[i].end());
		f[i] = vector<int>(nodes[i].size() + 5);
	}
	vector<int> ans(nq), ord(nq);
	iota(all(ord), 0);
	sort(all(ord), [&](int i, int j){return get<2>(q[i]) > get<2>(q[j]);});
	sort(all(a), [&](auto f, auto s){
		return get<2>(f) > get<2>(s);
	});
	int j = 0;
	for (int i : ord)
	{
		auto [x, y, z] = q[i];
		while (j < n && get<2>(a[j]) >= z) 
		{
			update(get<0>(a[j]), get<1>(a[j]));
			j++;
		}
		ans[i] = get(x, y);
	}
	for (int i : ans) cout << i << '\n';
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	while (t--) solve();
	return 0;
}

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