oj.uz

Submission #126962

# Submission time Handle Problem Language Result Execution time Memory
126962 2019-07-08T17:09:29 Z Mahmoud_Adel Examination (JOI19_examination) C++14
0 / 100
 703 ms 11020 KB 
#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<ll, null_type, less<ll>, rb_tree_tag, 
tree_order_statistics_node_update> oset;
const int N = 1e5+5;
ll n, m, ans[N];
pair<ll, ll> 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, ll> a, pair<ll, ll> 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);
	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);
		//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+1)-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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 703 ms 11020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 703 ms 11020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -