Submission #124406

#	Time	Username	Problem	Language	Result	Execution time	Memory
124406		naderjemel	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	7 / 100	744 ms	23072 KiB

worst_reporter3

#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 (stderr)

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 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 81