oj.uz

Submission #49735

# Submission time Handle Problem Language Result Execution time Memory
49735 2018-06-02T11:09:24 Z longcqt Worst Reporter 3 (JOI18_worst_reporter3) C++11
0 / 100
 1600 ms 32540 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1600 ms 32540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 32540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Incorrect 1600 ms 32540 KB Output isn't correct
2 Halted 0 ms 0 KB -