Submission #774987

#	Time	Username	Problem	Language	Result	Execution time	Memory
774987		nhphan0505	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	12 / 100	34 ms	16716 KiB

worst_reporter3

#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pii;
#define fi first
#define se second
#define gcd __gcd
#define endl '\n'
const int N=500050,M=1000000007;
const ll INF=0x3f3f3f3f3f3f3f3f;

ll n, q, d[N], u[N], t, l, r;

ll pos(ll i, ll t){return t/u[i]*u[i]-i;}

ll lower(ll t, ll x){
	ll l=-1, r=n+1;
	while(r-l>1){
		ll m=l+r>>1;
		if(pos(m, t)<=x) r=m;
		else l=m;
	}
	return r;
}

ll upper(ll t, ll x){
	ll l=-1, r=n+1;
	while(r-l>1){
		ll m=l+r>>1;
		if(pos(m, t)>=x) l=m;
		else r=m;
	}
	return l;
}

signed main(){
	ios_base::sync_with_stdio(NULL); 
	cin.tie(nullptr); cout.tie(nullptr);
	cin>>n>>q;
	for(ll i=1; i<=n; ++i) cin>>d[i];
	u[0]=1;
	for(ll i=1; i<=n; ++i){
		ll need=(d[i]+u[i-1]-1)/u[i-1];
		u[i]=need*u[i-1];
		// cout<<u[i]<<endl;
	}
	while(q--){
		cin>>t>>l>>r;
		ll up=upper(t, l);
		ll lo=lower(t, r);
		if(pos(lo, t)>=l && pos(lo, t)<=r) cout<<up-lo+1<<endl;
		else cout<<"0\n";
		// cout<<lo<<" "<<up<<endl;
	}
    return 0;
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'll lower(ll, ll)':
worst_reporter3.cpp:20:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |   ll m=l+r>>1;
      |        ~^~
worst_reporter3.cpp: In function 'll upper(ll, ll)':
worst_reporter3.cpp:30:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |   ll m=l+r>>1;
      |        ~^~

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