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

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;
}

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

If you have TLE on 17-th test , try to use clang compiler. For me it worked))

instead map use unordered_map

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

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)

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

Is it possible to solve this problem using SQRT-decomposition ?
0.5 second is a very tight limit and in-spite of minor optimizations and fast I/O my code having complexity of O (N * sqrt (N)) is getting TLE on test case 17.  I am just curious about the possibility.

I have tests many tests,with which I have found my program's mistakes,and maybe this tests can help you:
4
+ 2
+ 309
- 2
+ 957
and the answer is:
2
1
309
3
but I got TLE at #18 now...

I have debug my program for two days,but I still cannot find any mistakes in my program.
I wrote a program in order to make random tests,and I have used the accepted program to get the right answer and compare it to my program's answer.The result is right....

Edited by author 20.06.2013 11:01

> 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