oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

flight Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

flight.html

Problem Description

Pusheen is a fat and lazy cat. However, he might occasionally fly around town with his helicopter.

One day, Pusheen realises that that a portion of town is populated with many high-rise buildings, along a straight line. In total, there are N buildings in total, each of them equally spaced 1 unit apart, measured from midpoint to midpoint. In addition, the ith building from the left will have height Hi units.

To past time, Pusheen decides to fly his helicopter there. He will pick a building A and fly to another building B. However, as Pusheen is not very good at flying, he is unable to fly between a pair of buildings if the elevation ratio is more than equal U. The elevation ratio between two buildings is the difference in height divided by the horizontal distance between them. For instance, the elevation ratio between two buildings i and j will be abs(Hi - Hj)/abs(i - j) where abs is the absolute function.

However, flying with a low elevation ratio is also very boring. As such, Pusheen wants to know how many pairs of buildings there are such that their elevation ratio is between L ≤ elevation ratio < U.

To clarify, Pusheen does not consider pair (A, B) and pair (B, A) as two separate pairs, since the buildings and elevation ratio are the same.

Input

The input will consist of 2 lines.

The first line will contain 3 integers, N, L and U.

The second line contain N integers, with the ith integer being Hi.

Output

Output a single integer, the number of pairs of buildings such that their elevation ratio is between L (inclusive) and U (exclusive).

Subtasks

For all testcases, 0 ≤ L < U ≤ 109 and 0 ≤ Hi ≤ 109.

Subtask 1 (27%): 2 ≤ N ≤ 2000.

Subtask 2 (26%): 2 ≤ N ≤ 100000, 0 < U - L ≤ 10.

Subtask 3 (47%): 2 ≤ N ≤ 100000. No further restrictions.

Subtask 4 (0%): Sample Testcase

Sample Testcase 1

Input

6 1 3
8 7 1 2 2 8

Output

7

Explanation

The pairs of buildings are (1, 2), (3, 4), (2, 4), (2, 5), (3, 6), (1, 4), (1, 5).

Tags

TW NPSC 2016

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
127133s256MBMinimum
226183s256MBMinimum
347383s256MBMinimum
4013s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o flight -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.