| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Hi,
Given an Array with N elements each element have 3 integers Say Ai,Bi,Ci.
you have to answer Q querys given in each query 3 integers X,Y,Z you have to say how many elements in the array satisfy Ai>=X , Bi>=Y Ci<=Z
N,Q<=10^5
I hope you help me or give me a hint, thanks.
You have to use segment tree and BS Tree their subtrees' roots being hashed (using perfect hashing !) and finally BS on answers while also balancing the red-black tree, and maintaining the fact that the sum is even if the number of subtrees' nodes are 2^p-1, where p is any prime number.
Also take into account that 64MB stack is not enough to recursively solve the problem. You gotta use an iterative method.
Can we use 3-D Binary Indexed Tree? We need to find number of points in the box {x, y, z | 0 <= x <= X, 0 <= y <= Y, 0 <= z <= Z}. To fill the tree we will to update N*log(N)*log(N)*log(N) points in 3-D which can be hashed.
Can you tell me how much memory 3D BIT needs when max value is 300,000 and number of elements N=100,000?
delete
then how can this be implemented?
I read an article that implemented the 2-D BIT using MAX^2 memory so I thought that the need MAX^3
delete
I'm afraid that I don't know how hash works,
can you give me an article for hash in C++
delete
anyway 100,000 * log(300,000) * log(300,000) * log(300,000) which is about 500 MB is too large memory.
You can just sort array (using your own compare function) and use binary search.
To better understanding imagine, that each element has only one integer.
Here is my solution.
I'm afraid your solution is incorrect.
It gives wrong answer for the test like this:
1
2 2 2
1
1 1 1
It should be 0, but your solution outputs 1.
But is it possible algorithm: sort + binary search for the first is greater than or equal? If not, tell why, please.
I'm pretty sure it's impossible. Let's assume that all elements of the array have different a[i]. In this case, binary search will find the first element comparing a[i] only. But it doesn't use any information about b[i] and c[i](I mean that for some elements, a[i] might fit the constrains but b[i] or c[i] might not).
Yes, of course. I understand my mistake. Thank you!
Life of programmers is not that easy :) ,your code gives Wrong Answers
There's an offline solution which uses O((N + Q) * log(N + Q) + Q * (log N)^2) time and O(Q + N * log N) space.
Let's assume that each element of the array is a point in 3-D space.
1)At first, shrink all the Y-coordinates.
2)Then build a segment tree for Y-coordinate and store vector with all Z-coordinates of points which are covered by the segment represented by the tree's node. Moreover, keep a Fenwick tree in each node. Initially, all points should be in the tree and each Fenwick tree should contain 1 at all the positions.
3)After that, you may use sweep algorithm line to answer the queries. There should be two types of event: a point disappearing and a query. Events have to be sorted in non-descending order of X-coordinate.
To process the point(X, Y, Z) disappearing event, just modify one element in respective Fenwick tree which represents (Y, Z) point(adding -1 there) in the segment tree.
To process a query event, simply calculate the sum in (Y, 0, MAX_Y, Z) rectangle using the segment tree.