Submission #474660

#	Time	Username	Problem	Language	Result	Execution time	Memory
474660		prvocislo	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	690 ms	29380 KiB

worst_reporter3

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
typedef long long ll;
using namespace std;

const int maxn = 5e5 + 5;
int n, q;
ll d[maxn], cnt[maxn];
// i-ty ucastnik sa kazdych cnt[i] sekund pohne o mv[i] dopredu
ll pos(int i, int t) // pozicia i v case t
{
	return ((ll)-i) + (t / cnt[i]) * 1ll * cnt[i];
}
int last(int x, int t) // najdi index posledneho ktory stoji <= x v case t
{
	int lo = 0, hi = n + 1;
	while (lo < hi)
	{
		int mi = (lo + hi) >> 1;
		if (pos(mi, t) <= x) hi = mi;
		else lo = mi + 1;
	}
	return lo;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> q;
	cnt[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		cin >> d[i];
		// ak sa i-1 pohne o d[i] krokov
		cnt[i] = ((d[i] + cnt[i - 1] - 1) / cnt[i - 1]) * cnt[i - 1];
	}
	while (q--)
	{
		int t, l, r;
		cin >> t >> l >> r;
		int ans = last(l - 1, t) - last(r, t);
		cout << ans << "\n";
	}
	return 0;
}

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