Submission #49243

#	Time	Username	Problem	Language	Result	Execution time	Memory
49243		spencercompton	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	1473 ms	262144 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll get(ll tim, ll ind, ll wait, ll m){
	return tim/wait * m - ind;
}
int main(){
	int n, q;
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> q;
	ll d[n+1];
	ll x[n+1];
	ll mov[n+1];
	d[0] = 1LL;
	x[0] = 1LL;
	mov[0] = 1LL;
	for(int i = 1; i<=n; i++){
		cin >> d[i];
		x[i] = (d[i]/mov[i-1])*x[i-1];
		if(d[i]%mov[i-1]!=0){
			x[i] += x[i-1];
		}
		mov[i] = x[i]/x[i-1]*mov[i-1];
	}
	for(int i = 0; i<q; i++){
		ll t, l, r;
		cin >> t >> l >> r;
		//binsearch for first person in range
		int lo = 0;
		int hi = n;
		while(lo<hi){
			int mid = (lo+hi)/2;
			if(get(t,mid,x[mid],mov[mid])<=r){
				hi = mid;
			}
			else{
				lo = mid+1;
			}
		}
		if(get(t,lo,x[lo],mov[lo])<l || get(t,lo,x[lo],mov[lo])>r){
			cout << 0 << "\n";
			continue;
		}
		int og = lo;
		lo = 0;
		hi = n;
		while(lo<hi){
			int mid = (lo+hi+1)/2;
			if(get(t,mid,x[mid],mov[mid])>=l){
				lo = mid;
			}
			else{
				hi = mid-1;
			}
		}
		cout << (hi-og+1) << "\n";
	}
}

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