ICPC Russia High Load Database

H. High Load Database

time limit per test2 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
Henry profiles a high load database migration script. The script is the list of n transactions. The i-th transaction consists of ai queries. Henry wants to split the script to the minimum possible number of batches, where each batch contains either one transaction or a sequence of consecutive transactions, and the total number of queries in each batch does not exceed t.

Unfortunately, Henry does not know the exact value of t for the production database, so he is going to estimate the minimum number of batches for q possible values of t: t1,t2,…,tq. Help Henry to calculate the number of transactions for each of them.

Input
The first line contains a single integer n — the number of transactions in the migration script (1≤n≤200000).

The second line consists of n integers a1,a2,…,an — the number of queries in each transaction (1≤ai; ∑ai≤106).

The third line contains an integer q — the number of queries (1≤q≤100000).

The fourth line contains q integers t1,t2,…,tq (1≤ti≤∑ai).

Output
Output q lines. The i-th line should contain the minimum possible number of batches, having at most ti queries each. If it is not possible to split the script into the batches for some ti, output “Impossible” instead.

Remember that you may not rearrange transactions, only group consecutive transactions in a batch.

Example
inputCopy
6
4 2 3 1 3 4
8
10 2 5 4 6 7 8 8
outputCopy
2
Impossible
4
5
4
3
3
3

先求前缀和之后二分，但是很明显可以卡掉。

但是我们想一下，如果我们记忆化最坏复杂度，可以发现：

q*(n+n/2+n/3+…+n/n)*log(n) ，里面不就是一个调和级数吗？

所以复杂度为： q * logn * logn

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10;
int n,q,a[N],res[N*10],vis[N],mx,s,x;
int find(int l,int r){
	int ll=l;
	while(l<r){
		int mid=l+r+1>>1;
		if(a[mid]-a[ll-1]<=x)	l=mid;
		else	r=mid-1;
	}
	return l;
} 
inline int solve(int x){
	s=0; int L=1,ans=0; a[n+1]=x;
	while(L<=n){
		L=find(L,n)+1;	ans++;
	}
	return ans;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){scanf("%d",&a[i]); mx=max(mx,a[i]);	a[i]+=a[i-1];}
	cin>>q;
	while(q--){
		scanf("%d",&x);	if(x<mx){puts("Impossible");	continue;}
		if(res[x]){printf("%d\n",res[x]);	continue;}
		res[x]=solve(x);	printf("%d\n",res[x]);
	}
	return 0;
}