Biscuits (examination version)

Background

One thirty in the morning , The day is just dawning ,ly On the battlefield , No lunch , Hungry, he dug out a bag of biscuits from his pencil box ......

This bag of biscuits has n block , They are respectively called No 1,2...n block , The first i The area of a biscuit is w [i], And w [i] Is strictly rising （ namely w [i + 1] > w [i]）.

ly Need to eat s Area of cookies , And he will only choose one piece to eat , Then the block is larger than s The part will be thrown away .

So diligent and thrifty ly Of course, I will choose the biscuit that wastes the least area to eat .

Besides , as everyone knows , Everything will change with the change of many factors , Of course ly The area of cookies to eat s No exception

therefore ly Will ask you q Time ： When the area of cookies he needs to eat is s [i] when , Which biscuit should he eat .

（ Be careful ： Each inquiry is independent , No The first i After the first inquiry , Cookies will disappear ; If more than one biscuit meets the requirements , Output the smallest piece ）

Input format

For each test point , There are three lines of input

first line , Enter two positive integers n, q (n, q <= 20'0000),n Indicates the number of cookies ,q Indicates the number of times to ask .

The second line , Input n A positive integer w [i],(w [i] <= 10'0000'0000) It means the first one i The area of a biscuit .

The third line , Input p A positive integer s [i], (s [i] <= 2'0000'0000), Express ly The first i During the first inquiry , The area of cookies to eat .

Output description

Just one line ：q A positive integer , The first i The number means ly The first i The number of biscuits to eat in this inquiry .

The sample input

Copy to Clipboard

5 3 1 3 4 6 8 1 6 5 

Sample output

Copy to Clipboard

1 4 4

#include<bits/stdc++.h> 
using namespace std;
const int N = 1e6 + 10;
const int INF = 1e9 + 10;
int w[N];
int sum[N];
int n,q;

int main(){
		
	cin >> n >> q;
	for(int i = 1;i <= n;i ++){
		cin >> w[i];
	}
	while(q--){
		int x;
		cin >> x;
		int pos = lower_bound(w + 1,w + 1 + n,x) - w - 1;
		
		cout << pos + 1 << " ";
	}
	cout << endl;
	
	
}