CodeForces 302B 2分

CodeForces 302B 二分

Eugeny loves listening to music. He has n songs in his play list. We know that song number i has the duration of t_{i c1 plays c2 plays c..., in the end the song number n plays cm moments of time when he liked a song. Now for each such moment he wants to know the number of the song that played at that moment. The moment x means that Eugeny wants to know which song was playing during the x-th minute of his listening to the play list.}

Help Eugeny and calculate the required numbers of songs.

Input

The first line contains two integers n, m (1?≤?n,?m?≤?10^{n lines contain pairs of integers. The i-th line contains integersc_(1?≤?c10.}

The next line contains m positive integers v_vv(i?<?m).

The moment of time v_v

Output

Print m integers — the i-th number must equal the number of the song that was playing during the v

Sample Input

1 22 81 16

11

4 91 22 11 12 21 2 3 4 5 6 7 8 9

112234444

题意：给定歌曲和播放时间和播放次数，求出某一分钟在播放那首歌曲

思路：二分。不二分超时

代码：

#include <stdio.h>#include <string.h>int n, m, now;long long c, t;long long time[100005];int main () {    memset(time, 0, sizeof(time));    scanf("%d%d", &n, &m);    for (int i = 1; i <= n; i ++) {scanf("%lld%lld", &c, &t);time[i] = time[i - 1] + c * t;    }    for (int i = 1; i <= m; i ++) {scanf("%d", &now);int l = 1, r = n;while (l <= r) {    int mid = (l + r) / 2;    if (now > time[mid - 1] && now <= time[mid]) {printf("%d\n", mid);break;    }    else if (now > time[mid]) {l = mid + 1;    }    else if (now <= time[mid - 1])r = mid;}    }    return 0;}