Problem S. 85. (December 2013)
S. 85. We are given a sequence of N positive integers a_{i}, with N100000 and 1a_{i}1000000000. We are looking for significant subsequences of this sequence. A subsequence is said to be significant, if
 it consists of some consecutive elements of the original sequence, and
 its central element is not less than a prescribed number C with 1C1000000000.
To get the central element of a subsequence, first sort the subsequence into nondecreasing order, then take
 either its middle element when the subsequence length is odd,
 or the not smaller element of the two middle elements when the subsequence length is even.
For example, the central element of the sequence {9,2,1,6} is 6, while the central element of the sequence {4,9,5} is 5.
Since a given sequence has in general a large number of significant subsequences, we are only interested in the number of these significant subsequences.
Your program should read the values of N and C from the first line of the standard input, then the actual elements of the sequence from the next line. Your program should write the number of significant subsequences in the first and only line of the standard output.
In the example, a sample input (``Példa bemenet'') and the corresponding output (``Példa kimenet'') are displayed. As an explanation, notice that the following subsequences are significant: {10}, {6}, {10,5}, {5,6}, {6,2}, {10,5,6} and {10,5,6,2}.
Scoring and bounds. You can obtain 1 point for a brief and proper documentation clearly describing your solution; 9 further points can be obtained provided that your program solves any arbitrary valid input within 1 second of running time.
Partial points can be obtained if your program yields a solution for 200 or 2000.
The source code (s85.pas, s85.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s85.txt, s85.pdf, ...)  also describing which developer environment to use for compiling the source should be submitted in a compressed file s85.zip.
(10 pont)
Deadline expired on 10 January 2014.
Sorry, the solution is available only in Hungarian. Google translation
Mintamegoldásnak Jákli Aida Karolina megoldását tesszük közzé. S85.zip
Illetve megjegyzem, hogy érdemes utánanézni az úgynevezett intervallumfának, vagy segment treenek. Közzéteszem Weisz Ambrus megoldását, illetve egy oktató anyagot a témáról. main.cpp Az anyag:
tree.docx
Statistics:
