http://www.spoj.com/problems/DQUERY/en/ I tried to solve this problem with divide and conquer.
But in spoj verdicts is segmentation fault. Here is my code.... http://ideone.com/8g7Lyl
Isn't complexity O(nlogn) in total???
# | User | Rating |
---|---|---|
1 | ecnerwala | 3648 |
2 | Benq | 3580 |
3 | orzdevinwang | 3570 |
4 | cnnfls_csy | 3569 |
5 | Geothermal | 3568 |
6 | tourist | 3565 |
7 | maroonrk | 3530 |
8 | Radewoosh | 3520 |
9 | Um_nik | 3481 |
10 | jiangly | 3467 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | adamant | 164 |
2 | awoo | 164 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 150 |
8 | SecondThread | 148 |
9 | pajenegod | 145 |
10 | BledDest | 144 |
http://www.spoj.com/problems/DQUERY/en/ I tried to solve this problem with divide and conquer.
But in spoj verdicts is segmentation fault. Here is my code.... http://ideone.com/8g7Lyl
Isn't complexity O(nlogn) in total???
Name |
---|
This can be done by divide and conquer. You need to process offline query in this question
In offline how?? can you give me hints or source code??
Well for that you have to sort input and query together . Give the input higher priority . whenever you encounter there is an input operation check if this number previously found or not . If so then change the value to 0 on that point and give one to your update position . And for query just normal segment tree sum .
for better understanding you can check my code here
btw you are using cin/cout . you can surely get TLE for that . change it to scanf/printf for safety .
First. To remove the Segmentation Fault just change the visited array's size to 1000000. Secondly, your code is still O(N*M), so it will get TL-e.