Submission #126958

#	Time	Username	Problem	Language	Result	Execution time	Memory
126958		Mahmoud_Adel	Examination (JOI19_examination)	C++14	0 / 100	689 ms	7072 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
#define f first
#define s second
typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, 
tree_order_statistics_node_update> oset;
const int N = 1e5+5;
int n, m, ans[N];
pair<int, int> p[N];
struct query
{
	int A, B, C, idx, ins;
};
bool cmX(query a, query b)
{
	return a.ins < b.ins;
}
bool cmC(query a, query b)
{
	return a.C < b.C;
}
bool cmXY(pair<int, int> a, pair<int, int> b)
{
	return a.f+a.s < b.f+b.s;
}
query q[N];
oset s;
int main()
{
	cin >> n >> m;
	for(int i=0; i<n; i++) cin >> p[i].f >> p[i].s, s.insert(p[i].s);
	for(int i=0; i<m; i++) cin >> q[i].A >> q[i].B >> q[i].C, q[i].idx = i;
	sort(p, p+n);
	int l = 0;
	for(int i=0; i<m; i++)
	{
		q[i].C = max(q[i].C, q[i].A+q[i].B);
		q[i].ins = q[i].C-q[i].B;
	}
	sort(q, q+m, cmX);
	for(int i=0; i<m; i++)
	{
		while(l < n && p[l].f < q[i].ins) s.erase(p[l].s), l++;
		ans[q[i].idx] = s.size()-s.order_of_key(q[i].B);
		//cout << q[i].idx << " | " << s.size() << " " << s.order_of_key(q[i].B) << endl;
	}
	sort(q, q+m, cmC);
	sort(p, p+n, cmXY);
	s.clear();
	for(int i=0; i<n; i++) s.insert(p[i].f);
	l = 0;
	for(int i=0; i<m; i++)
	{
		if(q[i].A+q[i].B >= q[i].C) continue;
		while(l < n && p[l].f+p[l].s < q[i].C) s.erase(p[l].f), l++;
		ans[q[i].idx] += s.order_of_key(q[i].ins)-s.order_of_key(q[i].A);
		//cout << q[i].idx << " | " << q[i].ins << " " << q[i].A << " | " << s.order_of_key(q[i].ins) << " " << s.order_of_key(q[i].A) << endl;
	}
	for(int i=0; i<m; i++) cout << ans[i] << endl;
	
}

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