Submission #102574

#	Time	Username	Problem	Language	Result	Execution time	Memory
102574		TMJN	Examination (JOI19_examination)	C++14	2 / 100	3015 ms	102200 KiB

examination

#include <bits/stdc++.h>
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

struct T{
	int data, sl, sr, tl, tr, next;
};

int N, Q, s[100000], t[100000], x, y, z;
vector<int>svec, tvec;
vector<T>tree;

void update(int k, int s, int t) {
	if (tree[k].sl <= s&&s <= tree[k].sr&&tree[k].tl <= t&&t <= tree[k].tr) {
		if (tree[k].sl == tree[k].sr&&tree[k].tl == tree[k].tr) {
			++tree[k].data;
		}
		else {
			if (tree[k].next == -1) {
				tree[k].next = tree.size();
				tree.push_back({ 0,tree[k].sl,(tree[k].sl + tree[k].sr) / 2,tree[k].tl,(tree[k].tl + tree[k].tr) / 2,-1 });
				tree.push_back({ 0,tree[k].sl,(tree[k].sl + tree[k].sr) / 2,(tree[k].tl + tree[k].tr) / 2 + 1,tree[k].tr,-1 });
				tree.push_back({ 0,(tree[k].sl + tree[k].sr) / 2 + 1,tree[k].sr,tree[k].tl,(tree[k].tl + tree[k].tr) / 2,-1 });
				tree.push_back({ 0,(tree[k].sl + tree[k].sr) / 2 + 1,tree[k].sr,(tree[k].tl + tree[k].tr) / 2 + 1,tree[k].tr,-1 });
			}
			update(tree[k].next, s, t);
			update(tree[k].next + 1, s, t);
			update(tree[k].next + 2, s, t);
			update(tree[k].next + 3, s, t);
			tree[k].data = tree[tree[k].next].data + tree[tree[k].next + 1].data + tree[tree[k].next + 2].data + tree[tree[k].next + 3].data;
		}
	}
}

int calc(int k) {
	if (tree[k].data == 0)return 0;
	if (svec[tree[k].sr] < x || tvec[tree[k].tr] < y || svec[tree[k].sr] + tvec[tree[k].tr] < z)return 0;
	if (x <= svec[tree[k].sl] && y <= tvec[tree[k].tl] && z <= svec[tree[k].sl] + tvec[tree[k].tl])return tree[k].data;
	return calc(tree[k].next) + calc(tree[k].next + 1) + calc(tree[k].next + 2) + calc(tree[k].next + 3);
}

int main() {
	cin >> N >> Q;
	for (int i = 0; i < N; ++i) {
		cin >> s[i] >> t[i];
		svec.push_back(s[i]);
		tvec.push_back(t[i]);
	}
	sort(svec.begin(), svec.end());
	svec.erase(unique(svec.begin(), svec.end()), svec.end());
	sort(tvec.begin(), tvec.end());
	tvec.erase(unique(tvec.begin(), tvec.end()), tvec.end());
	tree.push_back({ 0,0,(int)svec.size() - 1,0,(int)tvec.size() - 1,-1 });
	for (int i = 0; i < N; ++i) {
		update(0, lower_bound(svec.begin(), svec.end(), s[i]) - svec.begin(), lower_bound(tvec.begin(), tvec.end(), t[i]) - tvec.begin());
	}
	for (int i = 0; i < Q; ++i) {
		cin >> x >> y >> z;
		cout << calc(0) << endl;
	}
}

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