This problem asks us either to search a set of notes or expand an input file so that we can determine which note is playing at a particularly time.
N is not too big so that the end of the song is no larger than 1,200,000. This suggests that a complex search (like that used in a proper search for the more challenging limits in the Silver version of the problem) is not necessary. We can even make an array with 1.2 million elements to store the note at each time. That is the approach of this solution. We will create an array whose values are just like the example from the task's text:
Beat: 0 1 2 3 4 5 6 ... <-- subscript
|----|----|----|----|----|----|--- ...
1111111111 : :
22222: : <-- array value
333333333333333:
We need only read in the notes and then expand them. My solution uses an auxiliary counter (j) to keep track of where the next note run is to be placed. Here is snippet of code that does just what we need:
fscanf (fin, "%d", &duration); for (k = 0; k < duration; k++) notes[j++] = i;
We read in a new duration and then lay down that many notes of value i.
NOTE WELL that this program uses "stdio". Those who use fstream will find that 'endl' is very, very slow for output and probably causes their programs to exceed the time limit. Using "\n" solves the problem.
Below is the complete program:
#include <stdio.h>
int notes[1200009];
main () {
FILE *fin = fopen ("snotes.in", "r");
FILE *fout = fopen ("snotes.out", "w");
int n, q, i, j, k, query;
fscanf (fin, "%d %d", &n, &q);
j = 0;
for (i = 1; i <= n; i++) {
int duration;
fscanf (fin, "%d", &duration);
for (k = 0; k < duration; k++)
notes[j++] = i;
}
for (i = 0; i < q; i++) {
fscanf (fin, "%d", &query);
fprintf (fout, "%d\n", notes[query]);
}
exit (0);
}