Submission #723337

#	Time	Username	Problem	Language	Result	Execution time	Memory
723337		mariowong	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	1376 ms	33124 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;

long long d[500005],p[500005],s[500005];
int main(){
	ios::sync_with_stdio(false);
	int n,q;
	cin >> n >> q;
	for (int i=1;i<=n;i++) cin >> d[i];
	p[0]=s[0]=d[0]=1;
	for (int i=1;i<=n;i++) p[i]=((d[i]-1)/s[i-1]+1)*p[i-1],s[i]=((d[i]-1)/s[i-1]+1)*s[i-1];
	for (int i=1;i<=q;i++){
		long long T,l,r;
		cin >> T >> l >> r;
		int bl=0,br=n;
		while (bl < br){
			int bmid=(bl+br+1)/2;
			if (T/p[bmid]*s[bmid]-bmid < l) br=bmid-1;
			else bl=bmid;
		}
		if (T/p[bl]*s[bl]-bl < l) bl--;
		int ansr=bl;
		bl=0,br=n;
		while (bl < br){
			int bmid=(bl+br)/2;
			if (T/p[bmid]*s[bmid]-bmid > r) bl=bmid+1;
			else br=bmid;
		}
		if (T/p[bl]*s[bl]-bl > r) bl++;
		int ansl=bl;
		cout << ansr-ansl+1 << "\n";	
	}
	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 81 / 81