oj.uz

Submission #622962

# Submission time Handle Problem Language Result Execution time Memory
622962 2022-08-04T22:02:45 Z izanbf Examination (JOI19_examination) C++14
20 / 100
 2064 ms 21916 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] = 1+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() + 5;

	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 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 12 ms 2132 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 236 ms 18724 KB Output is correct
2 Correct 223 ms 18740 KB Output is correct
3 Correct 237 ms 18748 KB Output is correct
4 Correct 179 ms 15548 KB Output is correct
5 Correct 173 ms 15448 KB Output is correct
6 Correct 83 ms 6124 KB Output is correct
7 Correct 229 ms 18788 KB Output is correct
8 Correct 212 ms 18620 KB Output is correct
9 Correct 213 ms 18256 KB Output is correct
10 Correct 146 ms 14944 KB Output is correct
11 Correct 145 ms 14884 KB Output is correct
12 Correct 65 ms 6084 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 18724 KB Output is correct
2 Correct 223 ms 18740 KB Output is correct
3 Correct 237 ms 18748 KB Output is correct
4 Correct 179 ms 15548 KB Output is correct
5 Correct 173 ms 15448 KB Output is correct
6 Correct 83 ms 6124 KB Output is correct
7 Correct 229 ms 18788 KB Output is correct
8 Correct 212 ms 18620 KB Output is correct
9 Correct 213 ms 18256 KB Output is correct
10 Correct 146 ms 14944 KB Output is correct
11 Correct 145 ms 14884 KB Output is correct
12 Correct 65 ms 6084 KB Output is correct
13 Incorrect 2064 ms 21916 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 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 12 ms 2132 KB Output isn't correct
8 Halted 0 ms 0 KB -