SAS001 - Apoorv and Maximum Inversion

Apoorv has an array of n integers.Inversion count of an array is defined by number of pair of indices(i,j) such that i<j and arr[i]>arr[j] .You are given an integer p.Apoorv has to find the subarray with maximum inversion count among all subarrays of size p.Apoorv find this job very tough so he turns to you for help.

Constraints :





First line contains two integers n and p.

Next line contains n space separated integers denoting the elements of the array.


Output two space separated integers first integer should be the starting index (1-based indexing) of the subarray and next integer would be the count of inversions in that subarray.In case there is a tie in maximum inversion count  print the smallest starting index among the subarrays having maximum inversion count.


10 5
15 51 44 44 76 50 29 88 48 50
5 6

hide comments
aman_sachin200: 2018-06-05 19:10:50

Nice problem :)

a2j007: 2018-03-27 08:24:01

Segment tree :D

ayush926: 2018-03-17 11:48:04

Nice question!
BIT+sliding window :)

shuvam_kedia: 2018-03-16 19:59:52

Nice problem :) sas1905 _/\_

amit_ranjan: 2017-12-31 11:51:09

My 175 on spoj :)

jaideeppyne: 2017-10-25 18:17:36

Segment tree + sliding window... try the problem "Inversion Count" in SPOJ before solving this.. that will be of great help ..HAPPY CODING! :D

divyanshjr: 2017-08-13 18:53:16

sas pro! Nice problem.. :)

choudharymohit: 2017-08-12 18:24:08

Sas pro!! _/\_
Good one :)

siddharth_0196: 2017-08-12 13:40:09

Nice question! Sas pro! _/\_
map -> TLE
unordered_map -> AC

yogahmad: 2017-08-12 05:05:55

Nice problem :)

Added by:sas1905
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)