Submission #553469

#	Time	Username	Problem	Language	Result	Execution time	Memory
553469		MohamedAhmed04	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	564 ms	25364 KiB

worst_reporter3

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 5e5 + 10 ;

long long arr[MAX] ;
int n , q ;

bool check(int idx , int x , int t)
{
	return (-idx + t / arr[idx] * arr[idx] <= x) ;
}

int calc(int x , int t)
{
	int l = 0 , r = n ;
	int ans = n+1 ;
	while(l <= r)
	{
		int mid = (l + r) >> 1 ;
		if(check(mid , x , t))
			ans = mid , r = mid-1 ;
		else
			l = mid+1 ;
	}
	return (n-ans+1) ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>q ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	arr[0] = 1 ;
	for(int i = 1 ; i <= n ; ++i)
		arr[i] = (arr[i] + arr[i-1] - 1) / arr[i-1] * arr[i-1] ;
	while(q--)
	{
		int t , l , r ;
		cin>>t>>l>>r ;
		cout<<calc(r , t) - calc(l-1 , t)<<"\n" ;
	}
	return 0 ;
}		

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