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

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

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

> 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

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 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!

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

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

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