Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Power Arrays

Revision en1, by jd_sal, 2019-08-20 22:43:50

Problem statement : Given an array of integers A of size N. An array is called power array if floor(maximum of array/2) >= all other elements of array. E.g [5,3,6,13] is a power array since 13/2 >= 5,3,6. Calculate how many subarrays of A are Power Arrays. Note : Single element can never be a power array.Constraints : 1<=N<=10^5 , 1<=A[i]<=10^5 .

I can think of a O(n^2) solution but it will definitely timeout. Any efficient solution? P.S : It's from a contest which has ended!


  Rev. Lang. By When Δ Comment
en1 English jd_sal 2019-08-20 22:43:50 499 Initial revision (published)