ADAFUROW  Ada and Furrows
As you might already know, Ada the Ladybug is a farmer. She has multiple furrows in which she grows vegetables. She also never grows multiple vegetables of the same kind in the same furrow. Ada sometime palnts a new vegetable, harveest a vegetable or asks for some aspect which two different furrows have in common (described in input).
Input
The first line of input will contain 1 ≤ Q ≤ 3*10^{5}, the number of queries.
Each of the next Q lines will contain ? x y: 0 ≤ x, y ≤ 2*10^{4}, and ? is one of: +  v ^ ! \ with following meaning:
+: Plants vegetable of kind y to furrow number x (note that there will never be multiple vegetables of the same kind in the same furrow)
: Harvests vegetable of kind y from furrow number x (note that there will always be a vegetable of that kind)
v: Finds out how many kinds of vegetables there are in furrows x and y.
^: Finds out how many kinds of vegetable are in both furrows (x, y)
!: Find out how many kinds of vegetables are in x and y BUT not in both of them at once.
\: Find out how many kinds of vegetable are in x but not in y
Output
For each query of the last four kinds, output the proper answer.
Example Input
10 + 1 4 ! 0 2 + 0 2 \ 0 2 ^ 0 1 v 2 0 + 2 4 ! 2 0 + 1 0 ! 0 2
Example Output
0 1 0 1 2 2
Example Input
15 + 0 2 ! 0 1 + 1 1 v 0 1 + 1 2 ! 1 0 ! 0 1 + 0 0 v 0 1 ^ 0 1 + 1 3 \ 1 0 \ 1 0 + 1 0  1 2
Example Output
1 2 1 1 3 1 2 2
Example Input
10 + 2 1 ! 3 1 ! 3 1 + 1 1 \ 2 0 + 3 1 v 2 3 ! 2 3  1 1 ^ 1 2
Example Output
0 0 1 1 0 0
hide comments
morass:
20171105 01:19:04
@julkas: Thanx.. anyway kinda sad the python doesn't fit in timelimit :/ 

julkas:
20171104 13:05:04
@morass. Good problem. Big truck beer from me. 8)) Last edit: 20171104 13:31:23 

julkas:
20171104 12:59:58
@Simes Think about a different approach to set operations. I think with PAS you can do it with 5s about. 

Simes:
20171102 22:43:18
Accepted... but with the slowest time by far. I wonder what I can do to improve it?


morass:
20171102 17:34:30
@febrianandawp: Yes, your solution is similar to judge solution. This problem is indeed that easy :P :) Have Nice Day ^_^ 

febrianandawp:
20171102 17:24:54
I just brute it with a little optimization and AC XD 

morass:
20171101 09:13:46
@nadstratosfer: Good day to you. Yes, it seems to be possible. I simply don't want to allow fast naive solution/heuristics to pass. Here the time limit is set to +/ 5*judge solution (and even more for solution of [Rampage] Blue.Mary). 

morass:
20171101 09:04:14
@[Rampage] Blue.Mary: Thank youm fixed (hopefully) 

[Rampage] Blue.Mary:
20171101 07:08:49
I don't know what does "O(1)" in your description mean. What's your complexity in total? If your program executes Q*N (where Q = 300000 and N = 20000) it will lead to TLE. My program executes far less operation than that. For your information, to the worst test case I can ever image, my program will execute about 10^8 operations, whereas Q*N is about 6*10^9. Last edit: 20171101 07:14:08 

nadstratosfer:
20171101 07:07:11
Blue.Mary, I TLE using mostly O(1) operations that Python has implemented in C, without creating unnecessary structures. Morass' problems have notoriously bad time limit settings for slower languages, barely ever allowing AC in PyPy let alone Python, and in this type of problem (loop with a bunch of statements, each costing interpreter time over every of 300,000 iterations) these particularily need relaxing. 
Added by:  Morass 
Date:  20171101 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 