oj.uz

Submission #156159

# Submission time Handle Problem Language Result Execution time Memory
156159 2019-10-03T21:26:05 Z luciocf Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 709 ms 25584 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e5+10;

int n;

int d[maxn];
int tempo[maxn];

int busca1(int t, int pos)
{
	int ini = 0, fim = n, ans = -1;

	while (ini <= fim)
	{
		int mid = (ini+fim)>>1;

		if ((t/tempo[mid])*tempo[mid] - mid >= pos) ans = mid, ini = mid+1;
		else fim = mid-1;
	}

	return ans;
}

int busca2(int t, int pos)
{
	int ini = 0, fim = n, ans = n+1;

	while (ini <= fim)
	{
		int mid = (ini+fim)>>1;

		if ((t/tempo[mid])*tempo[mid] - mid <= pos) ans = mid, fim = mid-1;
		else ini = mid+1;
	}

	return ans;
}

int main(void)
{
	int q;
	scanf("%d %d", &n, &q);

	for (int i = 1; i <= n; i++)
		scanf("%d", &d[i]);

	tempo[0] = 1, tempo[1] = d[1];
	for (int i = 2; i <= n; i++)
	{
		int x = d[i]/tempo[i-1];

		if (d[i]%tempo[i-1] != 0) x++;

		tempo[i] = x*tempo[i-1];
	}

	for (int i = 1; i <= q; i++)
	{
		int t, l, r;
		scanf("%d %d %d", &t, &l, &r);

		int R = busca2(t, r);
		int L = busca1(t, l);

		if (R > L) printf("0\n");
		else printf("%d\n", L-R+1);
	}
}

Compilation message

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
worst_reporter3.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &d[i]);
   ~~~~~^~~~~~~~~~~~~
worst_reporter3.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &t, &l, &r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 7496 KB Output is correct
2 Correct 674 ms 22752 KB Output is correct
3 Correct 671 ms 22680 KB Output is correct
4 Correct 678 ms 22936 KB Output is correct
5 Correct 700 ms 22740 KB Output is correct
6 Correct 709 ms 22736 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 7496 KB Output is correct
2 Correct 674 ms 22752 KB Output is correct
3 Correct 671 ms 22680 KB Output is correct
4 Correct 678 ms 22936 KB Output is correct
5 Correct 700 ms 22740 KB Output is correct
6 Correct 709 ms 22736 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 248 KB Output is correct
10 Correct 3 ms 412 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 467 ms 21116 KB Output is correct
14 Correct 479 ms 21872 KB Output is correct
15 Correct 450 ms 20444 KB Output is correct
16 Correct 463 ms 20984 KB Output is correct
17 Correct 596 ms 25332 KB Output is correct
18 Correct 601 ms 25336 KB Output is correct
19 Correct 597 ms 25420 KB Output is correct
20 Correct 611 ms 25452 KB Output is correct
21 Correct 600 ms 25208 KB Output is correct
22 Correct 602 ms 25280 KB Output is correct
23 Correct 604 ms 25196 KB Output is correct
24 Correct 611 ms 25584 KB Output is correct
25 Correct 688 ms 22904 KB Output is correct
26 Correct 678 ms 22688 KB Output is correct
27 Correct 636 ms 24720 KB Output is correct
28 Correct 653 ms 25220 KB Output is correct
29 Correct 614 ms 24720 KB Output is correct
30 Correct 649 ms 24868 KB Output is correct
31 Correct 643 ms 25124 KB Output is correct
32 Correct 540 ms 21496 KB Output is correct
33 Correct 2 ms 376 KB Output is correct