Submission #112267

#	Time	Username	Problem	Language	Result	Execution time	Memory
112267		JustInCase	Examination (JOI19_examination)	C++17	100 / 100	2092 ms	11904 KiB

examination

#include <bits/stdc++.h>

const int32_t MAX_N = 1e5;
const int32_t MAX_Q = 1e5;
const int32_t BUCKET_SIZE = 316;

struct Query {
	int32_t a, b, c, ind;
	
	bool operator< (const Query &o) const {
		int32_t bucket = a / BUCKET_SIZE;
		int32_t oBucket = o.a / BUCKET_SIZE;

		if(bucket == oBucket) {
			return b < o.b;
		}

		return bucket < oBucket;
	}
};

struct IndexTree {
	int32_t treeSize;
	int32_t data[2 * MAX_N + 5];

	void init(int32_t _treeSize) {
		treeSize = _treeSize;
	}

	void update(int32_t ind, int32_t val) {
		while(ind <= treeSize) {
			data[ind] += val;
			ind += (ind & (-ind));
		}
	}

	int32_t query(int32_t ind) {
		int32_t ans = 0;

		while(ind >= 1) {
			ans += data[ind];
			ind -= (ind & (-ind));
		}

		return ans;
	}
};

int32_t allAs[MAX_N + 5], allBs[MAX_N + 5], allCs[MAX_N + 5], newCs[MAX_N + 5], c[MAX_N + 5];
int32_t cnt[MAX_N + 5], ans[MAX_Q + 5];
std::pair< int32_t, int32_t > a[MAX_N + 5], b[MAX_N + 5];
Query qs[MAX_Q + 5];
IndexTree indTree;

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int32_t n, q;
	std::cin >> n >> q;

	for(int32_t i = 0; i < n; i++) {
		std::cin >> a[i].first >> b[i].first;

		allAs[i] = a[i].first;
		a[i].second = i;

		allBs[i] = b[i].first;
		b[i].second = i;
		
		c[i] = a[i].first + b[i].first;
		allCs[i] = a[i].first + b[i].first;
	}

	std::sort(allAs, allAs + n);
	std::sort(a, a + n);
	std::sort(allBs, allBs + n);
	std::sort(b, b + n);
	std::sort(allCs, allCs + n);
	
	for(int32_t i = 0; i < n; i++) {
		a[i].first = std::lower_bound(allAs, allAs + n, a[i].first) - allAs;
		b[i].first = std::lower_bound(allBs, allBs + n, b[i].first) - allBs;
		c[i] = std::lower_bound(allCs, allCs + n, c[i]) - allCs;
	}

	for(int32_t i = 0; i < q; i++) {
		int32_t u, v, t;
		std::cin >> u >> v >> t;
		
		qs[i].a = std::lower_bound(allAs, allAs + n, u) - allAs;
		qs[i].b = std::lower_bound(allBs, allBs + n, v) - allBs;
		qs[i].c = std::lower_bound(allCs, allCs + n, t) - allCs;
		qs[i].ind = i;
	}
	std::sort(qs, qs + q);

	indTree.init(n);
	int32_t indA = n - 1, indB = n - 1;
	for(int32_t i = 0; i < q; i++) {
		while(indA >= qs[i].a) {
			cnt[a[indA].second]++;
			if(cnt[a[indA].second] == 2) {
				indTree.update(c[a[indA].second] + 1, 1);
			}

			indA--;
		}

		while(indA + 1 < qs[i].a) {
			indA++;
			
			cnt[a[indA].second]--;
			if(cnt[a[indA].second] == 1) {
				indTree.update(c[a[indA].second] + 1, -1);
			}
		}

		while(indB >= qs[i].b) {
			cnt[b[indB].second]++;

			if(cnt[b[indB].second] == 2) {
				indTree.update(c[b[indB].second] + 1, 1);
			}

			indB--;
		}

		while(indB + 1 < qs[i].b) {
			indB++;
			
			cnt[b[indB].second]--;
			if(cnt[b[indB].second] == 1) {
				indTree.update(c[b[indB].second] + 1, -1);
			}
		}

		ans[qs[i].ind] = indTree.query(indTree.treeSize) - indTree.query(qs[i].c);
	}

	for(int32_t i = 0; i < q; i++) {
		std::cout << ans[i] << '\n';
	}
}

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