oj.uz

Submission #124411

# Submission time Handle Problem Language Result Execution time Memory
124411 2019-07-03T09:58:25 Z naderjemel Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 745 ms 25504 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define INF 1e9
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<pair<int,int> > vii;
 
vi ds,jump;
int pos[1005][1005];
int main(){
	int n,q; 
	scanf("%d%d",&n,&q);
	ds.pb(1);
	for(int i=1;i<=n;i++){
		int h; scanf("%d",&h);
		ds.pb(h);

	}
	jump.pb(1);
	for(int i=1;i<=n;i++){
		if(jump[i-1]>=ds[i]){
			jump.pb(jump[i-1]);
		}
		else if(jump[i-1]==1) jump.pb(ds[i]);
		else{
			int h=ds[i]/jump[i-1];
			if(ds[i]%jump[i-1]==0) jump.pb(jump[i-1]*h);
			else jump.pb(jump[i-1]*(h+1));
		}
	}
	//for(int i=0;i<=n;i++) printf("%d ", jump[i]); printf("\n");
	while(q--){
		int t,l,r; scanf("%d%d%d",&t,&l,&r);
		int st=-1,en=-1,lo=0,hi=n;
		while(lo<=hi){
			int mid=(lo+hi)/2;
			int times=t/jump[mid];
			ll mv=jump[mid]*times;
			ll pos=mv+(ll)(mid*-1);
			if(pos>=(ll)l && pos<=(ll)r){
				st=mid;
				hi=mid-1;
			}
			else if(pos<(ll)l) hi=mid-1;
			else lo=mid+1;
		}
		if(st==-1){
			printf("0\n");
			continue;
		}
		lo=st,hi=n;
		while(lo<=hi){
			int mid=(lo+hi)/2;
			int times=t/jump[mid];
			ll mv=jump[mid]*times;
			ll pos=mv+(ll)(mid*-1);
			if(pos>=(ll)l && pos<=(ll)r){
				en=mid;
				lo=mid+1;
			}
			else if(pos<(ll)l) hi=mid-1; 
			else lo=mid+1;
		}
		//printf("at T=%d st=%d en=%d\n", t,st,en);
		printf("%d\n", en-st+1);
	}
	return 0;
}

Compilation message

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:17: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:20:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int h; scanf("%d",&h);
          ~~~~~^~~~~~~~~
worst_reporter3.cpp:38:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int t,l,r; scanf("%d%d%d",&t,&l,&r);
              ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 710 ms 7364 KB Output is correct
2 Correct 721 ms 7392 KB Output is correct
3 Correct 720 ms 7340 KB Output is correct
4 Correct 716 ms 7348 KB Output is correct
5 Correct 715 ms 7536 KB Output is correct
6 Correct 714 ms 7384 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 710 ms 7364 KB Output is correct
2 Correct 721 ms 7392 KB Output is correct
3 Correct 720 ms 7340 KB Output is correct
4 Correct 716 ms 7348 KB Output is correct
5 Correct 715 ms 7536 KB Output is correct
6 Correct 714 ms 7384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 256 KB Output is correct
13 Correct 450 ms 21396 KB Output is correct
14 Correct 463 ms 21928 KB Output is correct
15 Correct 425 ms 20580 KB Output is correct
16 Correct 448 ms 21156 KB Output is correct
17 Correct 628 ms 25400 KB Output is correct
18 Correct 629 ms 25364 KB Output is correct
19 Correct 628 ms 25504 KB Output is correct
20 Correct 623 ms 25396 KB Output is correct
21 Correct 624 ms 25412 KB Output is correct
22 Correct 683 ms 25440 KB Output is correct
23 Correct 629 ms 25368 KB Output is correct
24 Correct 638 ms 25488 KB Output is correct
25 Correct 745 ms 22776 KB Output is correct
26 Correct 729 ms 22880 KB Output is correct
27 Correct 677 ms 25056 KB Output is correct
28 Correct 674 ms 25332 KB Output is correct
29 Correct 665 ms 24836 KB Output is correct
30 Correct 705 ms 24928 KB Output is correct
31 Correct 698 ms 25328 KB Output is correct
32 Correct 597 ms 21424 KB Output is correct
33 Correct 2 ms 256 KB Output is correct