ADAFUROW - Ada and Furrows

no tags 

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*105, the number of queries.

Each of the next Q lines will contain ? x y: 0 ≤ x, y ≤ 2*104, 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: 2017-11-05 01:19:04

@julkas: Thanx.. anyway kinda sad the python doesn't fit in time-limit :/

julkas: 2017-11-04 13:05:04

@morass. Good problem. Big truck beer from me. 8-))

Last edit: 2017-11-04 13:31:23
julkas: 2017-11-04 12:59:58

@Simes Think about a different approach to set operations. I think with PAS you can do it with 5s about.

Simes: 2017-11-02 22:43:18

Accepted... but with the slowest time by far. I wonder what I can do to improve it?

edit: Thank you so much @Junk and @Pranay. I don't feel so bad now.

Last edit: 2017-11-06 10:24:37
morass: 2017-11-02 17:34:30

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

febrianandawp: 2017-11-02 17:24:54

I just brute it with a little optimization and AC XD

morass: 2017-11-01 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: 2017-11-01 09:04:14

@[Rampage] Blue.Mary: Thank youm fixed (hopefully)

[Rampage] Blue.Mary: 2017-11-01 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: 2017-11-01 07:14:08
nadstratosfer: 2017-11-01 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:2017-11-01
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All