Submission #216067

#	Time	Username	Problem	Language	Result	Execution time	Memory
216067		someone_aa	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	0 / 100	2083 ms	24484 KiB

worst_reporter3

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 500100;
ll d[maxn], n, q;
ll blocksize[maxn];

ll f(int i, int t) {
	return (-i) + (t/blocksize[i]) * blocksize[i];
}

int main() {
	cin>>n>>q;
	for(int i=1;i<=n;i++) {
		cin>>d[i];
	}

	blocksize[0] = 1;
	blocksize[1] = d[1];
	for(int i=2;i<=n;i++) {
		blocksize[i] = blocksize[i-1] * int((d[i]+blocksize[i-1]-1)/(blocksize[i-1]));
		//cout<<i<<": "<<blocksize[i]<<" = "<<blocksize[i-1]<<" * "<<(d[i]+blocksize[i-1]-1)/(blocksize[i-1])<<"\n";
	}

	int qt, ql, qr;
	while(q--) {
		cin>>qt>>ql>>qr;
		/*for(int i=0;i<=n;i++) {
			cout<<i<<": "<<f(i, qt)<<"\n";
		}*/

		if(f(0, qt) < ql || f(n, qt) > qr) {
			cout<<"0\n";
			continue;
		}

		int index1 = n;
		for(int cekor=n/2;cekor>0;cekor/=2) {
			while(index1-cekor>=0 && f(index1-cekor, qt) <= qr) index1-=cekor;
		}

		int index2 = 0;
		for(int cekor=n/2;cekor>0;cekor/=2) {
			while(index2+cekor<=n && f(index2+cekor, qt) >= ql) index2+=cekor;
		}
		
		if(index1 > index2) swap(index1, index2);

		cout<<(index2-index1+1)<<"\n";
	}
}

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