Find length of longest subsection with all element less than k and q query

Question

1.00/5 (1 vote)

See more:

Given an integer sequence consisting of N elements a1, a2, … , aN and Q queries, each query is an integer K.

Requirements: For each query, determine the longest consecutive subsequence on the sequence A such that all the elements of that subsequence are not greater than K.

N, Q <= 10^5

| a[i] |<= 10^9

| K | <= 10^9

For example:

INP

6 4

-2 5 6 10 -5 0

-10

5

-4

11

OUT

0

2

1

6

explain

for K = -10 , there are no subsegments that satisfy

for K = 5 , have the segment [a1, a2] or [a5, a6]

What I have tried:

I tried to use DSU but no success

Posted 21-Jun-22 15:32pm

Huyền Nguyễn 2022

Updated 22-Jun-22 3:20am

Add a Solution

Comments

Patrice T 21-Jun-22 22:27pm

"I tried to use DSU but no success"
Try to show your work so far.

2 solutions

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CPallini · Answer 1 · 2022-06-21T20:14:00

Solution 1

You know, it reduces in finding the indices of the items a[i] satisfying a[i] >= k.
Once you have them, you may find the result as max(a[i+1]-a[i]+1).

Posted 21-Jun-22 20:14pm

CPallini

Comments

Huyền Nguyễn 2022 22-Jun-22 7:54am

Can you say more about this?

CPallini 22-Jun-22 8:28am

Search the first item, say a[i]>=k then search for the next one, say a[j]>=k, with j>i. The subsequence length is len=j-i+1.
Then set i=j and repeat the above operations. In the process, maintain the maximum found length.

Patrice T · Answer 2 · 2022-06-22T03:20:00

Quote:
I tried to use DSU but no success

This is a typical problem from a challenge site, the rule of thumb is that the solutions are never 'there is a standard feature that give the answer', you always have to craft the solution with an ad hoc algorithm.

A first approach is always : solve the problem by hand with short sample data, then solve again with more data until you have a good understanding of the problem. Then you translate you algorithm to code.

The most obvious solution for this problem is the brute force.
For every Q, check the list of integers.

If you want real help, show you work so far and explain its problems.

Find length of longest subsection with all element less than k and q query

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

Find length of longest subsection with all element less than k and q query

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

Existing Members

...or Join us