Submission #914708

#	Time	Username	Problem	Language	Result	Execution time	Memory
914708		WongYiKai	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	464 ms	25428 KiB

worst_reporter3

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

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n,q;
	cin >> n >> q;
	ll cycle[n+1];
	cycle[0] = 1;
	for (int i=0;i<n;i++){
		ll temp;
		cin >> temp;
		ll ii = i+1;
		if (temp <= cycle[i]) cycle[ii] = cycle[i];
		else cycle[ii] = temp+cycle[i]-(temp-1)%cycle[i]-1;
	}
	for (int i=0;i<q;i++){
		ll t,l,r;
		cin >> t >> l >> r;
		ll l2 = 0,r2 = n+1;
		while (l2<r2){
			ll m = l2+(r2-l2)/2;
			ll pos = -m + (t/cycle[m])*cycle[m];
			if (pos<=r) r2 = m;
			else l2 = m+1;
		}
		ll l3=0,r3=n+1;
		while (l3<r3){
			ll m = l3+(r3-l3)/2;
			ll pos = -m + (t/cycle[m])*cycle[m];
			if (pos>=l) l3=m+1;
			else r3=m;
		}
		cout << max(0LL,l3-l2) << "\n";
	}
}

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