Submission #49735

#	Time	Username	Problem	Language	Result	Execution time	Memory
49735		longcqt	Worst Reporter 3 (JOI18_worst_reporter3)	C++11	0 / 100	1600 ms	32540 KiB

worst_reporter3

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 1;

int n, q;
long long d[N], t[N], l[N];

int f(int x, int ti)
{
	int le = 0, ri = n;
	int res = n + 1;
	while (le <= ri)
	{
		int mid = (le + ri)/2;
		int k = floor((double)ti/(double)t[mid]);
		long long y = -mid + k*l[mid];
		if (y <= x)
		{
			res = mid;
			ri = mid - 1;
		}
		else le = mid + 1;
	}
	return res;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) cin >> d[i];
	t[0] = 1;
	l[0] = 1;
	t[1] = d[1];
	l[1] = d[1];
	for (int  i = 2; i <= n; ++i)
		if (d[i] < d[i - 1])
			t[i] = t[i - 1], l[i] = l[i - 1];
		else
		{
			int k = trunc(ceil((double)d[i]/(double)l[i - 1]));
		//	cout << ceil(5/2) << endl;
			//cout << k <<' ' << t[i - 1] <<' ' << l[i - 1] << endl;
			t[i] = k*t[i - 1];
			l[i] = k*l[i - 1];
		}
	for (int i = 1; i <= n; ++i) cout << t[i] <<' ' << l[i] << endl;
	int ti, le, ri;
	for (int i = 1; i <= q; ++i)
	{
		cin >> ti >> le >> ri;
		//cout << f(le - 1, ti) <<' ' << f(ri, ti) << '\n';
		cout << f(le - 1, ti) - f(ri, ti) << '\n';
	}
}

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