Submission #712811

#	Time	Username	Problem	Language	Result	Execution time	Memory
712811		Gromp15	Examination (JOI19_examination)	C++17	100 / 100	810 ms	95556 KiB

examination

#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
struct fenwick {
	int n;
	vector<int> bit;
	fenwick() {}
	void resize(int a) {
		n = a, bit.resize(a+1);
	}
	void update(int pos, int x) {
		pos++;
		for (; pos <= n; pos += pos&-pos) {
			bit[pos] += x;
		}
	}
	int sum(int pos) {
		int s = 0;
		while (pos) {
			s += bit[pos], pos -= pos&-pos;
		}
		return s;
	}
	int query(int l, int r) {
		return sum(r+1) - sum(l);
	}
};
struct seg {
	int N;
	vector<fenwick> tree;
	vector<vector<int>> vals;
	vector<int> who;
	vector<int> L, R;
	seg(const vector<ar<int, 2>> &pts) {
		int each = 1;
		for (int i = 1; i < sz(pts); i++) each += pts[i][0] != pts[i-1][0];
		N = 1<<(__lg(each)+1);
		tree.resize(2*N), vals.resize(2*N), who.resize(each), L.resize(2*N, 1e9), R.resize(2*N, -1e9);
		for (int i = 0, c = 0; i < sz(pts); i++, c++) {
			int r = i;
			while (r+1 < sz(pts) && pts[r+1][0] == pts[r][0]) r++;
			for (int j = i; j <= r; j++) {
				vals[c+N].push_back(pts[j][1]);
			}
			tree[c+N].resize(r-i+1), L[c+N] = pts[i][0], R[c+N] = pts[i][0];
			who[c] = pts[i][0];
			i = r;
		}
		for (int i = N-1; i >= 1; i--) {
			merge(all(vals[i*2]), all(vals[i*2+1]), back_inserter(vals[i]));
			vals[i].erase(unique(all(vals[i])), vals[i].end());
			tree[i].resize(sz(vals[i]));
			L[i] = min(L[i*2], L[i*2+1]);
			R[i] = max(R[i*2], R[i*2+1]);
		}
	}
	void update(int x, int y, int v) {
		auto it = lower_bound(all(who), x);
		assert(it != who.end() && *it == x);
		int pos = it - who.begin();
		for (int i = pos+N; i; i >>= 1) {
			auto it2 = lower_bound(all(vals[i]), y);
			assert(it2 != vals[i].end() && *it2 == y);
			tree[i].update(it2 - vals[i].begin(), v);
		}
	}
	int query(int node, int x, int y) {
		if (R[node] < x) return 0;
		if (L[node] >= x) {
			auto it = lower_bound(all(vals[node]), y);
			if (it != vals[node].end()) {
				return tree[node].query(it - vals[node].begin(), sz(vals[node]) - 1);
			}
			return 0;
		}
		return query(node*2, x, y) + query(node*2+1, x, y);
	}
};
void test_case() {
	int n, q;
	cin >> n >> q;
	vector<ar<int, 2>> pts(n);
	for (auto &x : pts) cin >> x[0] >> x[1];
	vector<ar<int, 4>> queries(q);
	for (auto &x : queries) cin >> x[0] >> x[1] >> x[2];
	for (int i = 0; i < q; i++) queries[i][3] = i;
	sort(all(queries), [&](const auto &A, const auto &B) { return A[2] > B[2]; });
	sort(all(pts), [&](const auto &A, const auto &B) { return A[0]+A[1] > B[0]+B[1]; });
	vector<int> ans(q);
	int to = -1;
	vector<ar<int, 2>> all_pts{pts};
	for (int i = 0; i < q; i++) all_pts.push_back({queries[i][0], queries[i][1]});
	sort(all(all_pts));
	all_pts.erase(unique(all(all_pts)), all_pts.end());
	seg st(all_pts);
	for (int i = 0; i < q; i++) {
		while (to+1 < n && pts[to+1][0] + pts[to+1][1] >= queries[i][2]) { 
			to++;
			st.update(pts[to][0], pts[to][1], 1);
		}
		ans[queries[i][3]] = st.query(1, queries[i][0], queries[i][1]);
	}
	for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
//    cin >> t;
    while (t--) test_case();
}

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