oj.uz

Submission #622959

# Submission time Handle Problem Language Result Execution time Memory
622959 2022-08-04T21:56:19 Z izanbf Examination (JOI19_examination) C++14
20 / 100
 1991 ms 24968 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;

		// 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 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 11 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 218 ms 18692 KB Output is correct
2 Correct 220 ms 21180 KB Output is correct
3 Correct 228 ms 21224 KB Output is correct
4 Correct 164 ms 17340 KB Output is correct
5 Correct 173 ms 17212 KB Output is correct
6 Correct 80 ms 7136 KB Output is correct
7 Correct 227 ms 21080 KB Output is correct
8 Correct 241 ms 21060 KB Output is correct
9 Correct 225 ms 20632 KB Output is correct
10 Correct 161 ms 16624 KB Output is correct
11 Correct 148 ms 16624 KB Output is correct
12 Correct 66 ms 7144 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 18692 KB Output is correct
2 Correct 220 ms 21180 KB Output is correct
3 Correct 228 ms 21224 KB Output is correct
4 Correct 164 ms 17340 KB Output is correct
5 Correct 173 ms 17212 KB Output is correct
6 Correct 80 ms 7136 KB Output is correct
7 Correct 227 ms 21080 KB Output is correct
8 Correct 241 ms 21060 KB Output is correct
9 Correct 225 ms 20632 KB Output is correct
10 Correct 161 ms 16624 KB Output is correct
11 Correct 148 ms 16624 KB Output is correct
12 Correct 66 ms 7144 KB Output is correct
13 Incorrect 1991 ms 24968 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 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 11 ms 2132 KB Output isn't correct
8 Halted 0 ms 0 KB -