oj.uz

Submission #124406

# Submission time Handle Problem Language Result Execution time Memory
124406 2019-07-03T09:47:30 Z naderjemel Worst Reporter 3 (JOI18_worst_reporter3) C++17
7 / 100
 744 ms 23072 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];
			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:37: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 719 ms 9560 KB Output is correct
2 Correct 728 ms 22960 KB Output is correct
3 Correct 731 ms 22920 KB Output is correct
4 Correct 744 ms 22968 KB Output is correct
5 Correct 740 ms 23072 KB Output is correct
6 Correct 742 ms 23020 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 719 ms 9560 KB Output is correct
2 Correct 728 ms 22960 KB Output is correct
3 Correct 731 ms 22920 KB Output is correct
4 Correct 744 ms 22968 KB Output is correct
5 Correct 740 ms 23072 KB Output is correct
6 Correct 742 ms 23020 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Incorrect 3 ms 376 KB Output isn't correct