Submission #208549

#	Time	Username	Problem	Language	Result	Execution time	Memory
208549		opukittpceno_hhr	Examination (JOI19_examination)	C++17	100 / 100	1880 ms	75496 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>
#include <ext/pb_ds/assoc_container.hpp>


using namespace std;
using namespace __gnu_pbds;

template<typename T>
using flex_set = tree<T, null_type, greater<T>, rb_tree_tag, tree_order_statistics_node_update>;  

struct Block {
	int sz;
	flex_set<pair<int, int>> kek;

	int solve(int x) {
		return kek.order_of_key(make_pair(x, -1));
	}

	void insert(int x) {
		sz++;
		kek.insert(make_pair(x, sz));
	}

	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];
	}
	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: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57