ChefTown Parade

All submissions for this problem are available.
ChefTown is the biggest city and the capital of ChefLand. There are N beautiful buildings: restaurants, museums, living houses with large kitchens and so on. Every building has its height. For every i (1<=i<=N) there is exactly one building with height i. The buildings are located in a single line from left to right. The height of ith building is H(i). The Mayor of ChefTown wants to organize a parade, where all great chefs will take part. A parade depends of its location. The location of a parade is a segment of consecutive buildings beginning near the building number L and ending near the building number R (1<=L<=R<=N). Any parade won't be interesting if it is not hold on an interesting segment of buildings. The segment of buildings is interesting if following are hold:
 Imagine, that we have a segment [L,R].
 Let K=RL+1 be the length of this segment, and B be a list of heights of the buildings that belong to this segment.
 Let's sort B in nondecreasing order.
 Segment [L,R] is interesting if B[i]B[i1]=1 for every i (2<=i<=K).
Now the Mayor of ChefTown is interested how many ways to organize an interesting parade of length W for ChefTown citizens. Help him and find out the number of different parades of length W, which can be hold in the city. Two parades ([L1,R1] and [L2,R2]) are considered to be different, if L1≠L2 or R1≠R2.
Input
Each input file consists of two lines, the first one contains two integers N and W (1<=N<=400000, 1<=W<=N). The second line contains N numbers H(i) (1<=i<=N)  the heights of the buildings.
Output
For each test case output a single integer  the number of interesting segments of buildings of length W.
Example
Input 1: 2 1 2 1 Input 2: 4 2 1 2 3 4 Output for Input 1: 2 Output for Input 2: 3
Author:  Rubanenko 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/CHEFTOWN 
Tags  Rubanenko datastructure deque sep12 
Date Added:  3082012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
@admin i am not getting this
@mishrapk answer is 2
@admin : The problem
@mishra_pk test incorrect:
@pva701 then what should be
@admin cant understand input
finally AC...
from where i should give
What is wrong with input and
gettin tle ...nyone can
Moreover, for N = 400000, W =
I have also N log N solution
Yeah, awkward.. That's why
@flareneos spoj servers are
IMP : Is the time limit not
roman_adm @ can you explain
@tanujrastogi: if you are
But I think it's a bit
i am getting TLE in nlogn
Definitely should be 1.5s2s
The time limit is too tight
i don't get this
plzzz give two more exmples.
@flareneos server is not
Finally AC .. just replaced
am not getting constraints
@devilz_007 "For every i
@roman_adm thanks for
@devilz_007 You're wellcome:)
lol... my C++ code runs but
1:Each input file consists of
@giorgi Yeah, as You can see
@pis113 TL may be caused by
@admin: Codes outputting 1
@admin: my code outputs 0 for
@karthikabinav and
@flareneos: 1 3 2 4 is a
Can anybody explain the input
Which ancient machine you
do we need to input several
worst case will be 40,000
Made O(N) solution, still
@admin i'm getting
@admin do we need to input
@admin do we need to input
As I go through the above
how does 2 1 2 1 give ans as
How is (1,2) of length 1 ?
@admin what should be the
I am getting RTE and this is
Is there a O(n) solution ??
@admin, the 4th bullet above
@Kurama Don't share your
@bodmas It's ok, since there
Is there a O(n) solution ??
@roman_adm, I'm sorry for
@adminwhen to stop reading
o(n) giving tle!!!!!!!
for input 40000 20000 my code
do we need to input several
someone answer please...
@roman_adm  check ur input
what is the input format
I hv done it in single
I hv done it in single
@nitajay28 You may also try
@avenger_coder Yeah,
@admin : seriously check your
@roman_adm I am also doing it
@roman_adm Problem above
hi guys, please help ..what's
@annem55 input must be from
@ecr123 is output for ur test
how many test cases are there
@roman_adm Is the answer for
@gokugohan i think 1 test
@admin test data might be
@admin please EXPLAIN input
Can the input be 10 2 3 4 3 4
Is 10 10 10 9 0 1 2 3 4 5 6 7
Is standard input/output fine
am using nlogn..... still
@devilz_007: You are just
@admin, according to the time
optimised input..!, output in
@roman_adm Is the answer for
for 3 1 3 1 2 is ans is 3 or
@Admin I have a
@ admin this is ridiculous
I am getting all d test cases
can any one tell me the
do recursive programs run
getting TLE for O(n) ... is
Any hint to get input faster
Very ambiguous problem
@nishchay2192 : am
nlogn can pass.... try to
pl explain 1 example
@admin : please clarify that
Was there rejudge? My
Can you please recheck test
Yes, I made my input reading
Still getting LTE ...when I'm
@EgorK Yes, the submissions
can nyone explain how to take
@admin : the test cases are
@admin: Time limit is very
I'm in the same situation as
@admin: Have the solutions
@mohamed_gaber what is the
Getting no response after
same code tle in java and ac
any body ..plz tell me the
it's ALWAYS console input...
anyone feels like giving a
submission id 1332645 got AC
"For every i (1<=i<=N) there
please try and give some more
Tried in every language
I am going to write this
@admin i solved this problem
@admin ..how come an O(n)
@admin, based on my first
@roman admin : very nice
I know the codechef judge is
I have a question:The program
Will there be a T indicating
Now this is really pissing
Hi, I am getting the
question would have been
@hitesh024 : you are right.
@admin test cases are still
can some help me why this
I first got my answer
I got AC and then, when
Great, I send again my