Submission #208545

#	Time	Username	Problem	Language	Result	Execution time	Memory
208545		opukittpceno_hhr	Examination (JOI19_examination)	C++17	2 / 100	3043 ms	15340 KiB

examination

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <random>

using namespace std;

struct Block {
	vector<int> hv;

	int solve(int x) {
		int ans = 0;
		for (auto t : hv) {
			ans += (t >= x);
		}
		return ans;
	}

	void insert(int x) {
		hv.push_back(x);
	}

	Block() {}
};

struct UltraFenw {
	int n;
	vector<Block> f;

	int cnt(int r, int x) {
		int ans = 0;
		for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {
			ans += f[i].solve(x);
		}
		return ans;
	}

	int cnt(int l, int r, int x) {
		return cnt(r, x) - cnt(l - 1, x);
	}

	void insert(int pos, int val) {
		for (int i = pos; i < n; i = i | (i + 1)) {
			f[i].insert(val);
		}
	}

	UltraFenw(int n_) {
		n = n_;
		f.resize(n);
	}
};

struct Query {
	int a, b, c;
	int ind;

	Query(int a_, int b_, int c_, int ind_) {
		a = a_;
		b = b_;
		c = c_;
		ind = ind_;
	};

	bool operator<(const Query &other) const {
		return c < other.c;
	}
};

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, q;
	cin >> n >> q;
	vector<pair<int, int>> a(n);
	for (auto &t : a) cin >> t.first >> t.second;
	sort(a.begin(), a.end());
	vector<int> f(n);
	vector<int> s(n);
	vector<int> sm(n);
	for (int i = 0; i < n; i++) {
		tie(f[i], s[i]) = a[i];
		sm[i] = f[i] + s[i];
	}
	// {
	// 	for (auto t : f) cerr << t << ' ';
	// 	cerr << endl;
	// 	for (auto t : s) cerr << t << ' ';
	// 	cerr << endl;
	// 	for (auto t : sm) cerr << t << ' ';
	// 	cerr << endl;
	// }
	UltraFenw fn(n);
	vector<Query> qs;
	for (int i = 0; i < q; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		qs.push_back(Query(x, y, z, i));
	}
	sort(qs.rbegin(), qs.rend());
	vector<int> ind(n);
	iota(ind.begin(), ind.end(), 0);
	sort(ind.rbegin(), ind.rend(), [&](int i, int j) {
		return sm[i] < sm[j];
	});
	int pnt = 0;
	vector<int> ans(q);
	for (auto t : qs) {
		while (pnt < n && sm[ind[pnt]] >= t.c) {
			fn.insert(ind[pnt], s[ind[pnt]]);
			pnt++;
		}
		int i = lower_bound(f.begin(), f.end(), t.a) - f.begin();
		ans[t.ind] = fn.cnt(i, n - 1, t.b);
	}
	for (auto t : ans) {
		cout << t << ' ';
	}
	cout << '\n';
}

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