oj.uz

답안 #126978

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
126978 2019-07-08T17:29:33 Z Mahmoud_Adel Examination (JOI19_examination) C++14
20 / 100
 850 ms 14464 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})-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

# 결과 실행 시간 메모리 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 25 ms 760 KB Output is correct
8 Correct 25 ms 760 KB Output is correct
9 Correct 26 ms 760 KB Output is correct
10 Correct 23 ms 760 KB Output is correct
11 Correct 24 ms 712 KB Output is correct
12 Incorrect 18 ms 760 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 812 ms 14216 KB Output is correct
2 Correct 794 ms 14212 KB Output is correct
3 Correct 761 ms 14176 KB Output is correct
4 Correct 694 ms 14464 KB Output is correct
5 Correct 714 ms 14372 KB Output is correct
6 Correct 572 ms 14200 KB Output is correct
7 Correct 732 ms 14404 KB Output is correct
8 Correct 745 ms 14312 KB Output is correct
9 Correct 703 ms 14300 KB Output is correct
10 Correct 655 ms 14172 KB Output is correct
11 Correct 686 ms 14064 KB Output is correct
12 Correct 575 ms 13960 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 812 ms 14216 KB Output is correct
2 Correct 794 ms 14212 KB Output is correct
3 Correct 761 ms 14176 KB Output is correct
4 Correct 694 ms 14464 KB Output is correct
5 Correct 714 ms 14372 KB Output is correct
6 Correct 572 ms 14200 KB Output is correct
7 Correct 732 ms 14404 KB Output is correct
8 Correct 745 ms 14312 KB Output is correct
9 Correct 703 ms 14300 KB Output is correct
10 Correct 655 ms 14172 KB Output is correct
11 Correct 686 ms 14064 KB Output is correct
12 Correct 575 ms 13960 KB Output is correct
13 Incorrect 850 ms 14164 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 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 25 ms 760 KB Output is correct
8 Correct 25 ms 760 KB Output is correct
9 Correct 26 ms 760 KB Output is correct
10 Correct 23 ms 760 KB Output is correct
11 Correct 24 ms 712 KB Output is correct
12 Incorrect 18 ms 760 KB Output isn't correct
13 Halted 0 ms 0 KB -