|
|
I`m using vector of segments. Everything is pretty fast, All the tests I could think of work correctly. EDIT: Finally, got a pretty good AC - Time: 0.234, Memory: 5 032 KB. (The problem was that I was not monitoring for segments getting empty) Edited by author 12.04.2023 23:40 10 + 24 + 27 + 9 + 24 + 12 - 24 - 24 - 12 - 27 - 9 24 3 3 3 3 3 3 9 9 1 5 + 8 + 6 + 8 - 8 - 8 8 2 2 2 6 9 + 10 + 10 + 10 - 10 - 10 + 5 - 10 - 5 + 123 10 10 10 10 10 5 5 1 123 The following test helped me to catch out-of-index run time exception in my solution: IN: 18 + 1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + 32 - 32 OUT: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 32 1 int make_test() { fstream inp("input2.txt", ios::out | ios::binary | ios::in | ios::trunc); if (!inp) { _Post_equals_last_error_ DWORD er = GetLastError(); cerr << er << '\n'; _getch(); exit(1); } int n = 100; inp << n << '\n'; srand(time(0)); for (int i = 0; i < n; i++) { int sign = rand() % 2; if (sign == 1 || i < 2) { int a = rand() % 300; while (find(simple.begin(), simple.end(), a) != simple.end()) { a = rand() % 300; } inp << "+ " << a << '\n'; v.push_back(a); } else if (v.size() > 1) { int a = rand() % v.size(); inp << "- " << v[a] << '\n'; v.erase(v.begin() + a); } } inp.close(); return 0; } If you have TLE on 17-th test , try to use clang compiler. For me it worked)) it is possible that the collection be empty after some operations! gcd(empty set)=1. Edited by author 31.03.2012 15:04 Thanks! I'm too get WA3, because didn't notice it instead map use unordered_map I used sqrt-decomposition and got AC in 358ms My idea was like this: 1. Keep an array of the elements we have so far 2. For each sqrt-size block of the array compute the GCD 3. To insert an element: append it to the array and update its block 4. To remove an element: swap the element to be deleted with last element (I used a set of pairs<value, index> to get them quickly) and update their blocks Insert (sqrt n) Delete (sqrt n) O(q sqrt n) where n is number of elements in the array Do you mean that after every insertion, we have to update the block containing the element as well as the block size? If block size is also updated, then shouldn't we have to update the whole array we've had so far? I used sqrt too but in a slightly different way from yours. I read all the queries and store all the values of query + to an array, decide the block size and compute GCD for each block. Then I loop the array again to answer the queries. If it is query +, I simply increase the counter x and call GCD(a[1..x]) (because I completely computed GCD of all blocks before). If it is query -, I erase x in the present array. Specifically, I recompute the GCD of the block without erased value x. This way caused me TLE on test #17, though :(( > I use the segment tree,but I can't find anything wrong... > Could you please give me some tests so that I can find out my program's problem? > Thank you. But now I got WA #5,and I have considered the following tests: 6 + 9 - 3 - 3 + 3 + 3 + 3 And I think the answer is: 9 9 9 9 9 3 But I still WA #5,Could someone can give me some hints or some tests? Edited by author 20.06.2013 10:52 Edited by author 20.06.2013 10:52 6 + 9 - 3 - 3 + 3 + 3 + 3 It`s impossible. Read the task again. Edited by author 15.08.2013 13:41 May be you don't use Long long in: 9 + 10 + 10 + 10 - 10 - 10 + 5 - 10 - 5 + 123 out: 10 10 10 10 10 5 5 1 123 GL. Sqrt decomposition works fine in this problem. I was barely able to pass the TL by using the segment tree. That part probably works OK, but what causes troubles is the way I locate the array index by given content value (i.e. we want do delete 8, so I search for 8's index and replace it with 0). For that purpose I was using map from STL and wasn't able to come up with anything better (except some hash-like storage). What did you use for that purpose or could you avoid such situation at all? Thanks. I solved by exactly the same algorithm, but got TLE 16-21. Then I just changed my cin to scanf and got AC for 0.218 Try ios::sync_with_stdio (false) . Report was it success or not. I am interested how useful is ios::sync_with_stdio(false) . Yes it does help. My solution (sqrt) was TLE 17. after this line it is AC 0.421. Just put this into main as the first line. thanks for the suggestion, I was too lazy to use scanf:) dont forget though that if you use this, then you cannot use printf and scanf in the same program with cin I use a sement tree, gave tle in test 17 and when I changed the scanf by the following "std :: ios :: sync_with_stdio (false)" I have acepted with time of 0.358 s 0.499 too close to comfort, i subitted first with GCC compiler got TLE than i submited with VC 2013 and got Accepted Edited by author 29.11.2016 18:01 just submitted code and got TLE on 15test, submitted same code after few minutes and got accepted. submitted again and got TLE on 24test for same code. I did it! I have TL 15 for a long time, but now I solved the problem. I use treap with gcd, but treap has a big constant and gcd works for O(log), so I write binary algorithm of calculating gcd instead of Euclid and it works! What algorithm did you use for gcd? can you paste only the gcd code here? I solved this problem by map for keeping count of numbers and dynamic segment tree. Is there any simpler solution that don't use data structures. I used segment tree with update func and HashMap for indexes of elements(+). Java AC 0.34sec Edited by author 27.01.2016 19:10 Edited by author 27.01.2016 19:38 Edited by author 27.01.2016 19:49 vector of segments and binary search also must work The same code with Dyramid got TLE at G++ and Clang and AC with 0.38 at Studio. I think the difference is to big, anybody now what is the issue? Edited by author 07.01.2015 07:16 0.234 at VS++2010 only segment tree (and 42 mb of memory). TL 15-16 at G++. Hi guys, i tryed to solve this problem with the treap (the randomized binary search tree ). It works for O(N*logN) , but i got TLE!!!!! For examlpe, i tryed to solve one problem (1208) with bruteforce (2^18 * 18), and i also got TLE, but on the CodeForces in max case, i got MAX : 0.3ms on the same complillers... Maybe you shouldn't put such small time limits? (Soz for Eng) For those who get TLE #17 try to use scanf/printf instead of cin/cout Thank you Petru, your advice helped me to pass from TLE 17 to TLE 29 :) |
|
|