Submission #627076

#	Time	Username	Problem	Language	Result	Execution time	Memory
627076		codr0	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	583 ms	7280 KiB

worst_reporter3

// Code by Parsa Eslami

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>

#define err(x) cerr<#x<<" : "<<x<<'\n'
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second
#define pb push_back
#define bit(i,j) ((j>>i)&1)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define all(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define dmid int mid=(r+l)/2
#define lc 2*id
#define rc 2*id+1

using namespace std;
const int N=5e5+4;
int r[N],d[N];
int n;

	int pos(int x,int t){
		return (-x+(t/r[x])*d[x]);
	}

	int32_t main(){
	iostream::sync_with_stdio(0); cin.tie(0);

	int q;
	cin>>n>>q;
	d[0]=1; r[0]=1;
	FOR(i,1,n) cin>>d[i];
	FOR(i,1,n){
		if(r[i-1]>1e9){ r[i]=2e9; continue;}
		/*if(d[i-1]==0){
			cout<<i<<'\n';
			FOR(j,0,i) cout<<d[j]<<" ";
			cout<<'\n';
			exit(0);
		}*/
		ll x=d[i]/d[i-1];
		if(d[i]%d[i-1]!=0) x++;
		/*if(x==0){
			cout<<i<<"&\n";
		}*/
		d[i]=x*d[i-1];
		x=x*r[i-1];
		if(x>1e9) r[i]=2e9;
		else r[i]=x;
	}
	/*FOR(i,0,n) cout<<r[i]<<" ";
	cout<<'\n';
	FOR(i,0,n) cout<<d[i]<<" ";
	cout<<'\n';*/
	FOR(i,1,q){
		int t,l,rr; cin>>t>>l>>rr;
		int ans=0;
		int L=-1,R=n+1;
		while(R-L>1){
			int mid=(R+L)/2;
			if(pos(mid,t)<=rr) R=mid;
			else L=mid;
		}
		ans+=(n+1-R);
		L=-1,R=n+1;
		while(R-L>1){
			int mid=(R+L)/2;
			if(pos(mid,t)<l) R=mid;
			else L=mid;
		}
		ans-=(n+1-R);
		cout<<ans<<'\n';
	}

	return 0;
	}

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