oj.uz

Submission #379274

# Submission time Handle Problem Language Result Execution time Memory
379274 2021-03-17T19:53:24 Z nafis_shifat Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 700 ms 29420 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e5+5;
const int inf=1e9;
int main() {
	int n,q;
	cin >> n >> q;

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

	ll jump[n + 2];
    jump[0] = 1;

    for(int i = 1; i <= n; i++) {
    	jump[i] = jump[i - 1] * ((d[i] + jump[i - 1] - 1) / jump[i - 1]);
    }


	while(q--) {
		ll t,l,r;
		scanf("%lld %lld %lld",&t,&l,&r);
		ll lo = 0;
		ll hi  = n;
		ll upb = -1,lwb = -1;

		while(lo <= hi) {
			ll mid = lo + hi >> 1;
			ll x = t / jump[mid];
			ll p = -mid + x * jump[mid];
			if(p <= r) {
				upb = mid;
				hi = mid - 1;
			} else {
				lo = mid + 1;
			}
		}


		lo = 0;
		hi = n;
		while(lo <= hi) {
			ll mid = lo + hi >> 1;
			ll x = t / jump[mid];
			ll p = -mid + x * jump[mid];
			if(p >= l) {
				lwb = mid;
				lo = mid + 1;
			} else {
				hi = mid - 1;
			}
		}

		
		ll ans;
		if(lwb < upb || lwb == -1 || upb == -1) ans = 0;
		else ans = lwb - upb + 1;

		printf("%lld\n",ans );
	}
	
}

Compilation message

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:30:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |    ll mid = lo + hi >> 1;
      |             ~~~^~~~
worst_reporter3.cpp:45:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |    ll mid = lo + hi >> 1;
      |             ~~~^~~~
worst_reporter3.cpp:12:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   12 |  for(int i = 1; i <= n; i++) scanf("%lld",&d[i]);
      |                              ~~~~~^~~~~~~~~~~~~~
worst_reporter3.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |   scanf("%lld %lld %lld",&t,&l,&r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 11116 KB Output is correct
2 Correct 700 ms 26704 KB Output is correct
3 Correct 679 ms 26836 KB Output is correct
4 Correct 698 ms 26608 KB Output is correct
5 Correct 676 ms 26732 KB Output is correct
6 Correct 659 ms 26900 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 11116 KB Output is correct
2 Correct 700 ms 26704 KB Output is correct
3 Correct 679 ms 26836 KB Output is correct
4 Correct 698 ms 26608 KB Output is correct
5 Correct 676 ms 26732 KB Output is correct
6 Correct 659 ms 26900 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 2 ms 364 KB Output is correct
13 Correct 428 ms 25092 KB Output is correct
14 Correct 419 ms 25708 KB Output is correct
15 Correct 414 ms 24556 KB Output is correct
16 Correct 449 ms 25068 KB Output is correct
17 Correct 502 ms 29184 KB Output is correct
18 Correct 524 ms 29312 KB Output is correct
19 Correct 532 ms 29224 KB Output is correct
20 Correct 510 ms 29164 KB Output is correct
21 Correct 507 ms 29420 KB Output is correct
22 Correct 527 ms 29292 KB Output is correct
23 Correct 508 ms 29164 KB Output is correct
24 Correct 520 ms 29292 KB Output is correct
25 Correct 660 ms 26632 KB Output is correct
26 Correct 650 ms 26732 KB Output is correct
27 Correct 567 ms 28748 KB Output is correct
28 Correct 551 ms 29236 KB Output is correct
29 Correct 583 ms 28664 KB Output is correct
30 Correct 570 ms 28908 KB Output is correct
31 Correct 552 ms 29116 KB Output is correct
32 Correct 532 ms 25196 KB Output is correct
33 Correct 1 ms 364 KB Output is correct