oj.uz

Submission #126976

# Submission time Handle Problem Language Result Execution time Memory
126976 2019-07-08T17:27:00 Z Mahmoud_Adel Examination (JOI19_examination) C++14
0 / 100
 796 ms 14216 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<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, -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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 26 ms 760 KB Output is correct
8 Correct 26 ms 892 KB Output is correct
9 Correct 26 ms 888 KB Output is correct
10 Correct 22 ms 888 KB Output is correct
11 Incorrect 23 ms 888 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 796 ms 14216 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 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 26 ms 760 KB Output is correct
8 Correct 26 ms 892 KB Output is correct
9 Correct 26 ms 888 KB Output is correct
10 Correct 22 ms 888 KB Output is correct
11 Incorrect 23 ms 888 KB Output isn't correct
12 Halted 0 ms 0 KB -