Wesley's Anger Contest 5 Problem 2 - MATH 137 at Squirreloo

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
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

At the University of Squirreloo, first-year squirrels in the math faculty have to take MATH 137: calculus, everyone's favourite branch of math! In this course they learn about convergent sequences, where values in a sequence get arbitrarily close to a limit. However, said sequences are infinite, and infinity is a concept too difficult to tackle immediately for our young squirrels, so they'll first discuss sequences of finite length - namely, an array of length N. We'll say an array A converges to a limit L with an accuracy of \epsilon if there exists a suffix B of A such that all elements in B differ from L by at most \epsilon. Given an array A of length N, the squirrels are given Q assignment questions of the form (L,\epsilon), and are tasked to determine whether or not A converges to L with an accuracy of \epsilon, and if so, to find the length of the longest suffix of A that fulfills the definition above.

Constraints

For this problem, you will be required to pass all the samples in order to receive any points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

1 \le N,Q \le 200\,000
0 \le |a_i| \le 10^9 for all 1 \le i \le N
0 \le |L|, \epsilon \le 10^9

Subtask 1 [18%]

1 \le N, Q \le 5\,000

Subtask 2 [82%]

No additional constraints.

Input Specification

On the first line will be two integers N and Q, the length of the array and the number of assignment questions respectively.

The second line will contain N integers a_1, \dots, a_n, the array A.

The following Q lines will each contain two integers L_i and \epsilon_i, the limit and accuracy to test for on the i^{th} assignment question.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output Q lines. The i^{th} line should contain the length of the longest suffix of A such that all elements in the suffix differ from L_i by at most \epsilon_i. If such a suffix does not exist, output 0.

Sample Input 1

8 5
1 5 4 6 -2 3 4 0
0 4
2 2
1 5
-1 0
5 5

Sample Output 1

4
3
8
0
3

Sample Input 2

5 5
1 2 3 4 5
5 1
4 1
2 2
2 3
1 5

Sample Output 2

2
3
0
5
5

Comments


  • 5
    Ynng11626  commented on Aug. 20, 2020, 11:51 p.m. edited

    off-by-ones make my brain hurt