제출 #131863

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
131863		tutis	Examination (JOI19_examination)	C++17	100 / 100	2250 ms	133832 KiB

examination

/*input
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
struct query
{
	int i;
	int a[3];
};
tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>A[202020];
int tim = 0;
void add(int x, int y)
{
	while (x < 202020)
	{
		A[x].insert({y, tim++});
		x += x & (-x);
	}
}
int get(int x, int y)
{
	x = min(x, 202019);
	int ans = 0;
	while (x > 0)
	{
		ans += A[x].size() - (A[x].order_of_key({y, -1}));
		x -= (x & (-x));
	}
	return ans;
}
int main()
{
	ios_base::sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	vector<int>a[n];
	map<int, int>M;
	for (int i = 0; i < n; i++)
	{
		int s, t;
		cin >> s >> t;
		M[t + 2] = -1;
		a[i] = {s, t, s + t};
	}
	sort(a, a + n, [&](vector<int>x, vector<int>y) {return x[0] > y[0];});
	query Q[q];
	for (int i = 0; i < q; i++)
	{
		Q[i].i = i;
		cin >> Q[i].a[0] >> Q[i].a[1] >> Q[i].a[2];
		M[Q[i].a[1] + 1] = -1;
	}
	sort(Q, Q + q, [&](query a, query b) {return a.a[0] > b.a[0];});
	int timer = 1;
	for (auto &i : M)
	{
		i.second = timer++;
	}
	int i = 0;
	int ans[q];
	for (query x : Q)
	{
		while (i < n && a[i][0] >= x.a[0])
		{
			add(M[a[i][1] + 2], a[i][2]);
			i++;
		}
		ans[x.i] = get(1e6, x.a[2]) - get(M[x.a[1] + 1], x.a[2]);
	}
	for (int i = 0; i < q; i++)
		cout << ans[i] << "\n";
}

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