Submission #49532

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49532	2018-05-30T21:22:39 Z	MatheusLealV	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	1037 ms	262144 KB

worst_reporter3

#include <bits/stdc++.h>
#define N 500050
using namespace std;

int n, q, D[N], F[N], g[N];

int upper_bound(int t, int T)
{
	int ini = 0, fim = n, mid, best = n + 1;

	while(fim >= ini)
	{
		mid = (ini + fim)/2;

		if(g[mid] * (t/g[mid]) - mid <= T)
		{
			best = mid;

			fim = mid - 1;
		}

		else ini = mid + 1;
	}

	return best;
}

int lower_bound(int t, int T)
{
	int ini = 0, fim = n, mid, best = n + 1;

	while(fim >= ini)
	{
		mid = (ini + fim)/2;

		if(g[mid] * (t/g[mid]) - mid < T)
		{
			best = mid;

			fim = mid - 1;
		}

		else ini = mid + 1;
	}

	return best;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>q;

	D[0] = 1, g[0] = 1;

	for(int i = 1; i <= n; i++)
	{
		cin>>D[i];

		g[i] = g[i - 1] * ceil((double)D[i]/(double) g[i - 1]);
	}

	for(int i = 1, T, A, B ; i <= q; i++)
	{
		cin>>T>>A>>B;

		cout<<abs(upper_bound(T, B) - lower_bound(T, A))<<"\n";
	}
}

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	634 ms	22704 KB	Output is correct
2	Correct	636 ms	38528 KB	Output is correct
3	Correct	811 ms	53784 KB	Output is correct
4	Correct	659 ms	69408 KB	Output is correct
5	Correct	718 ms	85000 KB	Output is correct
6	Correct	637 ms	100456 KB	Output is correct

Subtask #2

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	100456 KB	Output is correct
2	Correct	3 ms	100456 KB	Output is correct
3	Correct	3 ms	100456 KB	Output is correct
4	Correct	2 ms	100456 KB	Output is correct
5	Correct	3 ms	100456 KB	Output is correct
6	Correct	4 ms	100456 KB	Output is correct

Subtask #3

81.0 / 81.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	634 ms	22704 KB	Output is correct
2	Correct	636 ms	38528 KB	Output is correct
3	Correct	811 ms	53784 KB	Output is correct
4	Correct	659 ms	69408 KB	Output is correct
5	Correct	718 ms	85000 KB	Output is correct
6	Correct	637 ms	100456 KB	Output is correct
7	Correct	5 ms	100456 KB	Output is correct
8	Correct	3 ms	100456 KB	Output is correct
9	Correct	3 ms	100456 KB	Output is correct
10	Correct	2 ms	100456 KB	Output is correct
11	Correct	3 ms	100456 KB	Output is correct
12	Correct	4 ms	100456 KB	Output is correct
13	Correct	536 ms	114636 KB	Output is correct
14	Correct	442 ms	131008 KB	Output is correct
15	Correct	543 ms	146436 KB	Output is correct
16	Correct	493 ms	162320 KB	Output is correct
17	Correct	541 ms	182196 KB	Output is correct
18	Correct	541 ms	200876 KB	Output is correct
19	Correct	542 ms	219564 KB	Output is correct
20	Correct	539 ms	238132 KB	Output is correct
21	Correct	570 ms	256784 KB	Output is correct
22	Correct	1037 ms	262144 KB	Output is correct
23	Correct	662 ms	262144 KB	Output is correct
24	Correct	715 ms	262144 KB	Output is correct
25	Correct	657 ms	262144 KB	Output is correct
26	Correct	756 ms	262144 KB	Output is correct
27	Correct	653 ms	262144 KB	Output is correct
28	Correct	644 ms	262144 KB	Output is correct
29	Correct	614 ms	262144 KB	Output is correct
30	Correct	539 ms	262144 KB	Output is correct
31	Correct	532 ms	262144 KB	Output is correct
32	Correct	481 ms	262144 KB	Output is correct
33	Correct	2 ms	262144 KB	Output is correct