제출 #1143552

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

examination

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class fenwick {
private:
	vector<int> arr, fenw;
public:
	int query(int i) {
		if (i == -1) return 0;
		int ans = 0;
		for (; i; i -= (i & (-i)))
			ans += fenw[i];
		return ans;
	}
	void add(int i, int x) {
		arr[i] += x;
		for (; i <= arr.size(); i += (i & (-i)))
			fenw[i] += x;
	}
	fenwick(int n) {
		fenw.assign(n + 1, 0);
		arr.assign(n + 1, 0);
	}
};

bool comp(vector<int> a, vector<int> b) { return ((a[0] == b[0]) ? (a[1] >= b[1]) : (a[0] >= b[0])); }
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	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) <= 9000000) {
		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(), comp);

		int m = arr.size();
		fenwick f(1e5);
		int cnt = 0;
		for (int i = 0; i < m; ++i)
			if (arr[i][1]) f.add(arr[i][2], 1), ++cnt;
			else res[arr[i][2]] = f.query(qr[arr[i][2]][1] - 1);
		for (auto x : res) cout << x << endl;
	}
}

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