Submission #126980

#	Time	Username	Problem	Language	Result	Execution time	Memory
126980		Mahmoud_Adel	Examination (JOI19_examination)	C++14	100 / 100	994 ms	19012 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<pair<ll, int>, null_type, less<pair<ll, int>>, rb_tree_tag, 
tree_order_statistics_node_update> oset;
const int N = 1e5+5;
ll n, m, ans[N];
pair<ll, pair<ll, int>> p[N];
struct query
{
	ll 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<ll, pair<ll, int>> a, pair<ll, pair<ll, int>> b)
{
	return a.f+a.s.f < b.f+b.s.f;
}
query q[N];
oset s;
int main()
{
	cin >> n >> m;
	for(int i=0; i<n; i++) cin >> p[i].f >> p[i].s.f, p[i].s.s = i, s.insert({p[i].s.f, i});
	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);
	ll 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, -1});
		//cout << q[i].idx << " | " << s.size() << " " << s.order_of_key({q[i].B, N}) << 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, p[i].s.s});
	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.f < q[i].C) s.erase({p[l].f, p[l].s.s}), l++;
		ans[q[i].idx] += s.order_of_key({q[i].ins, -1})-s.order_of_key({q[i].A, -1});
		//cout << q[i].idx << " | " << q[i].ins << " " << q[i].A << " | " << s.order_of_key({q[i].ins+1, -1}) << " " << s.order_of_key({q[i].A, -1}) << endl;
	}
	for(int i=0; i<m; i++) cout << ans[i] << endl;
	
}

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