MWC '15 #4 P3: Salt

View as PDF

Submit solution

Points: 6 (partial)
Time limit: 0.1s
Java 8 0.5s
Python 0.5s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

After failing his accounting, physics and engineering tests all in one day, aurpine has decided to give you a problem! The problem is as follows.

There are N grains of salt, labelled 1 to N. The nth grain is located at the coordinate (X_n, Y_n). Two grains won't occupy the same coordinate (because that's crazy!).

You are to answer Q queries. There are two types of queries.

  • 1 x y – if there is a piece of salt at (x, y) output salty, otherwise output bland.
  • 2 X x – output the number of pieces of salt with an x-coordinate of x.
  • 2 Y y – output the number of pieces of salt with a y-coordinate of y.

Input Specification

Input will initiate with two space separated integers N and Q on a single line.

N lines follow with two space separated integers, X_n and Y_n, the coordinate of the nth grain of salt.

Q lines follow, in the queries form explained above.

Note: fast input may be required.


Subtask 1 [10%]

1 \le N, Q \le 100

1 \le X_n, Y_n \le 10^3

Subtask 2 [30%]

1 \le N,Q \le 10\,000

1 \le X_n, Y_n \le 10^3

Subtask 3 [60%]

1 \le N,Q \le 10\,000

1 \le X_n, Y_n \le 10^9

Output Specification

Q lines, one for each query.

Sample Input

5 4
1 2
3 5
4 3
4 5
4 7
1 2 1
1 1 2
2 X 4
2 Y 5

Sample Output


Explanation for Sample Output

There is no grain of salt at (2, 1). There is a grain of salt at (1, 2). There are 3 grains with an x-coordinate of 4. There are 2 grains with a y-coordinate of 5.


  • 0
    fed80  commented on April 16, 2016, 1:37 p.m. edited

    The explanation says there are 4 grains with a y coordinate of 5, but in fact there are 2.

    • 1
      aurpine  commented on April 16, 2016, 1:46 p.m.

      Nice catch. Thanks! Problem statement fixed.

  • 2
    aurpine  commented on April 16, 2016, 1:33 p.m.

    The second batch has been fixed. (there were duplicates) Sorry.

    • -3
      kushanzaveri  commented on April 17, 2016, 4:42 p.m.

      I can't believe you've done this.