Submission #1035210

#TimeUsernameProblemLanguageResultExecution timeMemory
1035210Alexabcde1Worst Reporter 3 (JOI18_worst_reporter3)C++14
100 / 100
791 ms29264 KiB
#include<bits/stdc++.h> using namespace std; long long n,q,a[500005],sttime[500005],t,l,r,mid,ll,rr; long long f(long long tt,long long k){ return ((tt)/sttime[k])*sttime[k]-k; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>q; for (int i=1;i<=n;i++) cin>>a[i]; sttime[1] = a[1]; for (int i=2;i<=n;i++){ sttime[i] = ((a[i]+sttime[i-1]-1)/sttime[i-1])*sttime[i-1]; } while (q--){ cin>>t>>l>>r; long long ans=0; long long ansl=1; long long ansr=n; if (f(t,1)<l) goto skip; if (r<f(t,n)) goto skip; ll=1; rr=n; while (ll<=rr){ mid=(ll+rr)/2; if (l<=f(t,mid)){ ansl=max(ansl,mid); ll=mid+1; } else rr=mid-1; } ll=1; rr=n; while (ll<=rr){ mid=(ll+rr)/2; if (f(t,mid)<=r){ ansr=min(ansr,mid); rr=mid-1; } else ll=mid+1; } if (ansl>=ansr) ans=ansl-ansr+1; skip:; /* for (int i=1;i<=n;i++){ if (l<=f(t,i)&&f(t,i)<=r) ans++; } */ if (l<=t && t<=r) ans++; cout<<ans<<endl; } } /* 6 1 11 36 28 80 98 66 190 171 210 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...