제출 #1143558

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

examination

#include<iostream>
#include<vector>
#include<algorithm>
#pragma GCC optimize("Ofast")
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);
	}
};

class state {
public:
	int x, y; bool v;
	state(int a, int b, int c) {}
	bool operator<(state const& o){
		return ((x == o.x) ? (v > o.v) : (x > o.x));
	}
};
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) <= 100000000) {
		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<state> arr;
		vector<int> res(q);
		for (auto x : a) {
			state c(x.first, 1, x.second);
			arr.push_back(c);
		}
		for (int i = 0; i < q; ++i) {
			state c(qr[i][0], 0, i);
			arr.push_back(c);
		}
		sort(arr.begin(), arr.end());

		int m = arr.size();
		fenwick f(1e5);
		int cnt = 0;
		for (int i = 0; i < m; ++i)
			if (arr[i].v) f.add(arr[i].y, 1), ++cnt;
			else res[arr[i].y] = f.query(qr[arr[i].y][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