Submission #1088976

#TimeUsernameProblemLanguageResultExecution timeMemory
1088976DobromirAngelovWorst Reporter 3 (JOI18_worst_reporter3)C++14
19 / 100
341 ms20820 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; const int MAXN=5e5+5; const int MAXQ=5e5+5; int n,q; int v[MAXN]; int getPos(int ind,int t) { return t/v[ind]*v[ind]-ind; } int bs(int x,int t) { int l=0,r=n; while(l<r) { int mid=(l+r+1)/2; if(getPos(mid,t)>=x) l=mid; else r=mid-1; } return l; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>q; for(int i=1;i<=n;i++) cin>>v[i]; for(int i=2;i<=n;i++) { v[i]=(v[i]+v[i-1]-1)/v[i-1]*v[i-1]; } for(int i=0;i<q;i++) { int t,l,r; cin>>t>>l>>r; int ind1=bs(r+1,t); int ind2=bs(l,t); int ans=0; if(l<=t && t<=r) ans++; ans+=ind2-ind1; cout<<ans<<endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...