Where is my suit
All submissions for this problem are available.
Deadpool has become famous among people of New York. People love his suit and want it badly. One fine morning Wade finds his suit missing and suspects someone living in his street to have robbed it. The street in which Wade lives can be defined by four integers L1, R1, L2 and R2.Deadpool wants his suit back, but he could only find the probable positions of the suit. You are given an array A of size N where any two indices in the array denote the position of the suit and there are Q queries you need to answer.
Your task is to count the number of pairs of indices (i, j) ,satisfying the following conditions:
The first line contains one integer N.
The second line contains N space-separated integers A1, A2, ..., AN.
The third line contains one integer Q.
Each of the next Q lines contains four integers L1, R1, L2 and R2, describing one query.
For each query print the answer in a separate line.
- 1 ≤ N,Q ≤ 50000
- 1 ≤ Ai ≤ N
- 1 ≤ L1 ≤ R1≤ N
- 1 ≤ L2 ≤ R2≤ N
Input: 7 1 5 2 1 7 2 2 8 1 3 4 5 2 3 5 7 1 4 3 7 2 6 4 7 1 6 2 5 3 3 6 7 4 5 1 4 2 3 4 5 Output: 1 2 5 6 6 2 2 0
Problem Setter : Shubham Chauhan
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.