oj.uz

Submission #622961

# Submission time Handle Problem Language Result Execution time Memory
622961 2022-08-04T21:59:41 Z izanbf Examination (JOI19_examination) C++14
20 / 100
 2044 ms 21908 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 12 ms 2140 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 18800 KB Output is correct
2 Correct 236 ms 18756 KB Output is correct
3 Correct 223 ms 18720 KB Output is correct
4 Correct 157 ms 15576 KB Output is correct
5 Correct 184 ms 15532 KB Output is correct
6 Correct 88 ms 6208 KB Output is correct
7 Correct 228 ms 18668 KB Output is correct
8 Correct 271 ms 18748 KB Output is correct
9 Correct 213 ms 18220 KB Output is correct
10 Correct 148 ms 14864 KB Output is correct
11 Correct 156 ms 14896 KB Output is correct
12 Correct 65 ms 6128 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 18800 KB Output is correct
2 Correct 236 ms 18756 KB Output is correct
3 Correct 223 ms 18720 KB Output is correct
4 Correct 157 ms 15576 KB Output is correct
5 Correct 184 ms 15532 KB Output is correct
6 Correct 88 ms 6208 KB Output is correct
7 Correct 228 ms 18668 KB Output is correct
8 Correct 271 ms 18748 KB Output is correct
9 Correct 213 ms 18220 KB Output is correct
10 Correct 148 ms 14864 KB Output is correct
11 Correct 156 ms 14896 KB Output is correct
12 Correct 65 ms 6128 KB Output is correct
13 Incorrect 2044 ms 21908 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 12 ms 2140 KB Output isn't correct
8 Halted 0 ms 0 KB -