Submission #917145

#TimeUsernameProblemLanguageResultExecution timeMemory
917145alexddWorst Reporter 3 (JOI18_worst_reporter3)C++17
12 / 100
2015 ms12188 KiB
#include<bits/stdc++.h> using namespace std; /*ifstream fin("input.in"); ofstream fout("output.out"); #define cin fin #define cout fout*/ #define int long long int n,q; int d[500005]; int p[500005]; int ultmare[500005]; int calc_cur(int i, int t) { return -i + (t/p[i]) * p[i]; } void calc_p() { int mxm=d[1]; p[1]=d[1]; ultmare[1]=1; for(int i=2;i<=n;i++) { if(d[i]>=mxm) { mxm=((d[i]-1)/mxm + 1)*mxm; p[i]=mxm; ultmare[i]=i; } else { ultmare[i]=ultmare[i-1]; } } } signed main() { ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>q; for(int i=1;i<=n;i++) cin>>d[i]; calc_p(); int le,ri,t; while(q--) { cin>>t>>le>>ri; int cnt=0; if(le<=t && t<=ri) cnt++; for(int i=1;i<=n;i++) { int cur = calc_cur(ultmare[i],t) - (i - ultmare[i]); if(cur<le) break; if(cur<=ri) cnt++; } cout<<cnt<<"\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...