제출 #1143545

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1143545		am_aadvik	Examination (JOI19_examination)	C++20	2 / 100	231 ms	21368 KiB

examination

#include<bits/stdc++.h>
#include<vector>
#include<algorithm>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> s;


int main()
{
	int n, q; cin >> n >> q;
	vector<pair<int, int>> a(n);
	vector<vector<int>> qr;
	for (int i = 0; i < n; ++i)
		cin >> a[i].first >> a[i].second;
	for (int x = 0; x < q; ++x) {
		int i, j, k; cin >> i >> j >> k;
		qr.push_back({ i,j,k });
	}

	if ((n * q) <= 10000000) {
		for (auto it : qr) {
			int cnt = 0, x = it[0];
			int y = it[1], z = it[2];
			for (auto i : a)
				if ((i.first >= x) && (i.second >= y) && ((i.first + i.second) >= z))
					++cnt;
			cout << cnt << endl;
		}
	}
	else {
		vector<vector<int>> arr;
		vector<int> res(q);
		for (auto x : a)
			arr.push_back({ x.first, 1, x.second });
		for (int i = 0; i < q; ++i)
			arr.push_back({ qr[i][0], 0, i });
		sort(arr.begin(), arr.end());
		int m = arr.size();
		for (int i = 0; i < m / 2; ++i) 
			swap(arr[i], arr[m - i - 1]);
		for (int i = 0; i < m; ++i)
			if (arr[i][1]) s.insert(arr[i][2]);
			else res[arr[i][2]] = s.size() - s.order_of_key(qr[arr[i][2]][1]);
		for (auto x : res) cout << x << endl;
	}

}

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