oj.uz

Submission #627396

# Submission time Handle Problem Language Result Execution time Memory
627396 2022-08-12T14:20:28 Z MilosMilutinovic Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 684 ms 25060 KB 
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i ++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i ++)
#define MP make_pair

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

#define int long long

int n, q, d[500005];
int calc(int i, int T)
{
	int coeff = T / d[i];
	return coeff * d[i] - i - 1;
}
signed main()
{
	scanf("%lld%lld", &n, &q);
	rep(i, n) scanf("%lld", &d[i]);
	rep(i, n) {
		if(i == 0) continue;
		d[i] = d[i - 1] * ((d[i] + d[i - 1] - 1) / d[i - 1]);
	}
	while(q--) {
		int T, L, R;
		scanf("%lld%lld%lld", &T, &L, &R);
		int l = -1, r = -1;
		{
			int low = 0, high = n - 1;
			while(low <= high) {
				int mid = low + high >> 1;
				if(calc(mid, T) <= R) l = mid, high = mid - 1;
				else low = mid + 1;
			}
		}
		{
			int low = 0, high = n - 1;
			while(low <= high) {
				int mid = low + high >> 1;
				if(calc(mid, T) >= L) r = mid, low = mid + 1;
				else high = mid - 1;
			}
		}
		int ans;
		if(l == -1 || calc(l, T) > R) ans = 0;
		else ans = r - l + 1;
		if(L <= T && T <= R) ans ++;
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:33:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |     int mid = low + high >> 1;
      |               ~~~~^~~~~~
worst_reporter3.cpp:41:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |     int mid = low + high >> 1;
      |               ~~~~^~~~~~
worst_reporter3.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  scanf("%lld%lld", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
worst_reporter3.cpp:21:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  rep(i, n) scanf("%lld", &d[i]);
      |            ~~~~~^~~~~~~~~~~~~~~
worst_reporter3.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   scanf("%lld%lld%lld", &T, &L, &R);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 624 ms 7100 KB Output is correct
2 Correct 684 ms 7168 KB Output is correct
3 Correct 622 ms 7140 KB Output is correct
4 Correct 634 ms 7120 KB Output is correct
5 Correct 628 ms 7148 KB Output is correct
6 Correct 617 ms 7104 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 624 ms 7100 KB Output is correct
2 Correct 684 ms 7168 KB Output is correct
3 Correct 622 ms 7140 KB Output is correct
4 Correct 634 ms 7120 KB Output is correct
5 Correct 628 ms 7148 KB Output is correct
6 Correct 617 ms 7104 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 1 ms 220 KB Output is correct
12 Correct 1 ms 224 KB Output is correct
13 Correct 380 ms 16136 KB Output is correct
14 Correct 510 ms 21736 KB Output is correct
15 Correct 395 ms 20352 KB Output is correct
16 Correct 476 ms 20872 KB Output is correct
17 Correct 537 ms 21088 KB Output is correct
18 Correct 577 ms 21772 KB Output is correct
19 Correct 580 ms 17116 KB Output is correct
20 Correct 452 ms 22748 KB Output is correct
21 Correct 473 ms 21312 KB Output is correct
22 Correct 502 ms 18484 KB Output is correct
23 Correct 511 ms 25060 KB Output is correct
24 Correct 610 ms 18152 KB Output is correct
25 Correct 601 ms 22580 KB Output is correct
26 Correct 676 ms 22568 KB Output is correct
27 Correct 534 ms 24744 KB Output is correct
28 Correct 527 ms 25052 KB Output is correct
29 Correct 518 ms 24568 KB Output is correct
30 Correct 530 ms 24676 KB Output is correct
31 Correct 564 ms 24908 KB Output is correct
32 Correct 494 ms 21192 KB Output is correct
33 Correct 1 ms 212 KB Output is correct