Submission #69769

#	Time	Username	Problem	Language	Result	Execution time	Memory
69769		yogahmad	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	1383 ms	207200 KiB

worst_reporter3

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
#define f first
#define s second
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a);
#define MOD 1000000007
#define MID (l+r)/2
#define ALL(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define mx 500003
#define pc(x) putchar_unlocked(x);
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> pbds;

long long n,a[mx],gerak[mx],setiap[mx],q,t,l,r;

long long cel(long long a,long long b){
	long long ret=a/b;
	if(a%b)ret++;
	return ret;
}

int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	setiap[0]=gerak[0]=1;
	gerak[1]=a[1];
	setiap[1]=a[1];
	for(int i=2;i<=n;i++){
		long long sem=cel(a[i],gerak[i-1]);
		setiap[i]=sem*setiap[i-1];
		gerak[i]=sem*gerak[i-1];
	}
	//for(int i=1;i<=n;i++)cout<<setiap[i]<<' '<<gerak[i]<<endl;
	while(q--){
		scanf("%lld%lld%lld",&t,&l,&r);
		int lo=0,hi=n,kiri=-1;
		while(lo<=hi){
			int mid=(lo+hi)>>1;
			long long brp=t/setiap[mid];
			brp=brp*gerak[mid];
			long long di=brp-mid;
			if(l<=di){
				lo=mid+1;
				kiri=mid;
			}
			else hi=mid-1;
		}
	//	debug(kiri);
		if(kiri==-1){
			puts("0");
			continue;
		}
		lo=0,hi=n;
		int kanan=-1;
		while(lo<=hi){
			int mid=(lo+hi)>>1;
			long long brp=t/setiap[mid];
			brp=brp*gerak[mid];
			long long di=brp-mid;
			if(di<=r){
				hi=mid-1;
				kanan=mid;
			}
			else lo=mid+1;
		}
		//debug(kanan);
		if(kanan==-1){
			puts("0");
			continue;
		}
		printf("%d\n",kiri-kanan+1);
	}
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:29:20: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  scanf("%d%d",&n,&q);
               ~~   ^
worst_reporter3.cpp:29:20: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
worst_reporter3.cpp:30:39: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  for(int i=1;i<=n;i++)scanf("%d",&a[i]);
                                  ~~~~~^
worst_reporter3.cpp:29: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:30:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%d",&a[i]);
                       ~~~~~^~~~~~~~~~~~
worst_reporter3.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld",&t,&l,&r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 81 / 81