Submission #1276238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276238		namhh	Worst Reporter 3 (JOI18_worst_reporter3)	C++20	100 / 100	341 ms	11228 KiB

worst_reporter3

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 5e5+5;
int n,q,d[N],hori[N];
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> q;
	for(int i = 1; i <= n; i++) cin >> d[i];
	hori[1] = d[1];
	for(int i = 2; i <= n; i++) hori[i] = ((d[i]+hori[i-1]-1)/hori[i-1])*hori[i-1];
	while(q--){
		int l,r,t;
		cin >> t >> l >> r;
		int l1 = 0;
		int r1 = n;
		int l2 = 1e9;
		int r2 = -1;
		while(l1 <= r1){
			int mid = (l1+r1)/2;
			int kaori;
			if(mid == 0) kaori = t;
			else kaori = hori[mid]*(t/hori[mid])-mid;
			if(kaori >= l){
				r2 = mid;
				l1 = mid+1;
			}
			else r1 = mid-1;
		}
		l1 = 0;
		r1 = n;
		while(l1 <= r1){
			int mid = (l1+r1)/2;
			int kaori;
			if(mid == 0) kaori = t;
			else kaori = hori[mid]*(t/hori[mid])-mid;
			if(kaori <= r){
				l2 = mid;
				r1 = mid-1;
			}
			else l1 = mid+1;
		}
		//cout << l2 << " " << r2 << "\n";
		if(r2 < l2) cout << 0 << "\n";
		else cout << r2-l2+1 << "\n";
	}
}

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