Submission #622961

#	Time	Username	Problem	Language	Result	Execution time	Memory
622961		izanbf	Examination (JOI19_examination)	C++14	20 / 100	2044 ms	21908 KiB

examination

#include <bits/stdc++.h>
using namespace std;

#define D(x) cerr << #x << " = " << x << ", "

struct Point {
	int x, y, z;
};

struct Query {
	int a, b, c, id;
};

const int B = 300;

struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n;

    FenwickTree(int n_) {
        this->n = n_;
        bit.assign(n, 0);
    }

    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

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

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int N, Q;
	cin >> N >> Q;

	set<int> values;

	vector<Point> pts(N);
	for (int i = 0; i < N; ++i) {
		Point& p = pts[i];
		cin >> p.x >> p.y;
		p.z = p.x + p.y;
		values.insert(p.x);
		values.insert(p.y);
		values.insert(p.z);
	}

	vector<Query> qs(Q);
	for (int i = 0; i < Q; ++i) {
		Query& q = qs[i];
		cin >> q.a >> q.b >> q.c;
		q.id = i;
		values.insert(q.a);
		values.insert(q.b);
		values.insert(q.c);
	}


	unordered_map<int,int> comp;
	for (int v : values) {
		comp[v] = comp.size();
	}

	for (Query& q : qs) {
		q.a = comp[q.a];
		q.b = comp[q.b];
		q.c = comp[q.c];
	}

	for (Point& p : pts) {
		p.x = comp[p.x];
		p.y = comp[p.y];
		p.z = comp[p.z];
	}

	int sz = comp.size() + 2;

	sort(qs.begin(), qs.end(), [](const Query& l, const Query& r) {
		return l.c < r.c;
	});

	sort(pts.begin(), pts.end(), [](const Point& l, const Point& r) {
		return l.z < r.z;
	});

	int blocks = (N+B-1)/B;
	vector<vector<Query>> block_queries(blocks);
	int j = 0;

	for (int block = 1; block < blocks; ++block) {
		int i = B*block;
		while (j < Q and qs[j].c <= pts[i].z) {
			block_queries[block-1].push_back(qs[j]);
			++j;
		}
	}
	while (j < Q) {
		block_queries.back().push_back(qs[j]);
		++j;
	}

	vector<int> ans(Q);

	FenwickTree ft(sz);

	for (int block = 0; block < blocks; ++block) {
		if (block_queries[block].empty()) continue;

		ft.bit.clear();

		// multiset<int> heights;

		vector<Point> in_block;
		in_block.reserve(B);
		for (int i = B*block; i < N and i < B*(block+1); ++i) {
			in_block.push_back(pts[i]);
		}

		vector<Point> over_block;
		over_block.reserve(N-B*block);
		for (int i = B*(block+1); i < N; ++i) {
			over_block.push_back(pts[i]);
			ft.add(pts[i].y, 1); // heights.insert(pts[i].y);
		}

		sort(over_block.begin(), over_block.end(), [&](const Point& l, const Point& r) {
			return l.x > r.x;
		});

		sort(block_queries[block].begin(), block_queries[block].end(), [&](const Query& l, const Query& r) {
			return l.a < r.a;
		});

		for (const Query& q : block_queries[block]) {
			int cnt_in = 0;

			// points in block
			for (const Point& p : in_block) {
				if (p.x >= q.a and p.y >= q.b and p.z >= q.c) ++cnt_in;
			}

			// points over block
			while ((not over_block.empty()) and over_block.back().x < q.a) {
				const Point& p = over_block.back();
				ft.add(p.y, -1); // heights.erase(heights.find(p.y));
				over_block.pop_back();
			}

			/*for (int y : heights) {
				if (y >= q.b) {
					++cnt_over;
				}
			}*/

			int cnt_over = ft.sum(q.b, sz-1);

			ans[q.id] = cnt_in + cnt_over;
		}
	}

	for (int i = 0; i < Q; ++i) {
		cout << ans[i] << '\n';
	}
}

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