oj.uz

Submission #622968

# Submission time Handle Problem Language Result Execution time Memory
622968 2022-08-04T22:13:30 Z izanbf Examination (JOI19_examination) C++14
2 / 100
 3000 ms 23484 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 k) {
        this->n = k;
        bit.assign(k, 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);
 
	for (int block = 0; block < blocks; ++block) {
		if (block_queries[block].empty()) continue;
 
		multiset<int> heights;

		FenwickTree ft(sz);
 
		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]);
			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;
			int cnt_over = 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();
				heights.erase(heights.find(p.y));
				over_block.pop_back();
			}
 
			for (int y : heights) {
				if (y >= q.b) {
					++cnt_over;
				}
			}
 
			// D(q.id), D(block), D(in_block.size()), D(over_block.size()), D(cnt_in), D(cnt_over) << endl;
 
			ans[q.id] = cnt_in + cnt_over;
		}
	}
 
	for (int i = 0; i < Q; ++i) {
		cout << ans[i] << '\n';
	}
}

Subtask #1
2.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 0 ms 212 KB Output is correct
7 Correct 35 ms 2300 KB Output is correct
8 Correct 34 ms 2220 KB Output is correct
9 Correct 33 ms 2260 KB Output is correct
10 Correct 27 ms 1748 KB Output is correct
11 Correct 26 ms 1804 KB Output is correct
12 Correct 24 ms 648 KB Output is correct
13 Correct 47 ms 2024 KB Output is correct
14 Correct 45 ms 2024 KB Output is correct
15 Correct 44 ms 2024 KB Output is correct
16 Correct 24 ms 1208 KB Output is correct
17 Correct 20 ms 1364 KB Output is correct
18 Correct 5 ms 596 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3054 ms 23484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3054 ms 23484 KB Time limit exceeded
2 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 0 ms 212 KB Output is correct
7 Correct 35 ms 2300 KB Output is correct
8 Correct 34 ms 2220 KB Output is correct
9 Correct 33 ms 2260 KB Output is correct
10 Correct 27 ms 1748 KB Output is correct
11 Correct 26 ms 1804 KB Output is correct
12 Correct 24 ms 648 KB Output is correct
13 Correct 47 ms 2024 KB Output is correct
14 Correct 45 ms 2024 KB Output is correct
15 Correct 44 ms 2024 KB Output is correct
16 Correct 24 ms 1208 KB Output is correct
17 Correct 20 ms 1364 KB Output is correct
18 Correct 5 ms 596 KB Output is correct
19 Execution timed out 3054 ms 23484 KB Time limit exceeded
20 Halted 0 ms 0 KB -