Submission #441871

#	Time	Username	Problem	Language	Result	Execution time	Memory
441871		dutch	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	997 ms	33228 KiB

worst_reporter3

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

const int INF = 2e9, MAXN = 5e5;

int n, q, d[MAXN], t[MAXN], s[MAXN];

int search(int x, int p){
	int i = -1;
	for(int j=1<<20; j/=2; ){
		if(i+j >= n) continue;
		i += j;
		if(- i - 1 + x / t[i] * s[i] < p) i -= j;
	}
	return i;
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> q;
	for(int i=0; i<n; ++i) cin >> d[i];

	fill(t, t+n, INF);
	t[0] = s[0] = d[0];

	for(int i=1; i<n; ++i){
		int m = ((d[i] + s[i-1] - 1) / s[i-1]);
		s[i] = m * s[i-1];
		t[i] = m * t[i-1];
		if(t[i] > INF) break;
	}

	while(q--){
		int x, l, r; cin >> x >> l >> r;
		cout << search(x, l) - search(x, r+1) + (l <= x && x <= r) << '\n';
	}
}

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