oj.uz

답안 #126977

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

# 결과 실행 시간 메모리 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 760 KB Output is correct
9 Correct 26 ms 764 KB Output is correct
10 Correct 22 ms 760 KB Output is correct
11 Correct 22 ms 784 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 789 ms 14308 KB Output is correct
2 Correct 825 ms 14200 KB Output is correct
3 Correct 798 ms 14432 KB Output is correct
4 Correct 690 ms 14200 KB Output is correct
5 Correct 705 ms 14296 KB Output is correct
6 Correct 578 ms 14328 KB Output is correct
7 Correct 752 ms 14268 KB Output is correct
8 Correct 765 ms 14456 KB Output is correct
9 Correct 728 ms 14360 KB Output is correct
10 Correct 737 ms 14072 KB Output is correct
11 Correct 703 ms 14064 KB Output is correct
12 Correct 561 ms 13944 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 789 ms 14308 KB Output is correct
2 Correct 825 ms 14200 KB Output is correct
3 Correct 798 ms 14432 KB Output is correct
4 Correct 690 ms 14200 KB Output is correct
5 Correct 705 ms 14296 KB Output is correct
6 Correct 578 ms 14328 KB Output is correct
7 Correct 752 ms 14268 KB Output is correct
8 Correct 765 ms 14456 KB Output is correct
9 Correct 728 ms 14360 KB Output is correct
10 Correct 737 ms 14072 KB Output is correct
11 Correct 703 ms 14064 KB Output is correct
12 Correct 561 ms 13944 KB Output is correct
13 Incorrect 866 ms 14348 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 26 ms 760 KB Output is correct
8 Correct 26 ms 760 KB Output is correct
9 Correct 26 ms 764 KB Output is correct
10 Correct 22 ms 760 KB Output is correct
11 Correct 22 ms 784 KB Output is correct
12 Incorrect 18 ms 760 KB Output isn't correct
13 Halted 0 ms 0 KB -