记录编号	571497	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[Codeforces 797E]Array Queries	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	5.423 s
提交时间	2022-05-25 20:44:56	内存使用	160.62 MiB

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int maxm = 405;
int f[maxn][maxm],a[maxn],n;
int main() {
    freopen("arrayque.in","r",stdin);
    freopen("arrayque.out","w",stdout);
	scanf("%d",&n);
	for(int i = 1;i <= n;++ i)scanf("%d",&a[i]);
	for(int k = 1;k < maxm;++ k) {
		for(int i = n;i;-- i) {
			if(i + a[i] + k > n)f[i][k] = 1;
			else f[i][k] = f[i + a[i] + k][k] + 1;
		}
	}
	int p,k,Q;
	scanf("%d",&Q);
	while(Q --) {
		scanf("%d%d",&p,&k);
		if(k >= maxm) {
			int ans = 0;
			for(;p <= n;p += a[p] + k)++ ans;
			printf("%d\n",ans);
		}
		else printf("%d\n",f[p][k]);
	}
	return 0;
}