Submission #914926

#TimeUsernameProblemLanguageResultExecution timeMemory
914926yhkhooWorst Reporter 3 (JOI18_worst_reporter3)C++17
19 / 100
470 ms26708 KiB
#include <bits/stdc++.h> using namespace std; #define int long long signed main(){ cin.tie(0); ios_base::sync_with_stdio(0); int n, q; cin >> n >> q; int d[n]; for(int i=0; i<n; i++){ cin >> d[i]; } int cyc[n+1]; int running=1; for(int i=0; i<=n; i++){ if(running <= 1000000000){ cyc[i] = running; running *= d[i]/running + (d[i]%running != 0); } else{ cyc[i] = 0; } } while(q--){ int t, l, r; cin >> t >> l >> r; int lo=0, hi=n, m1; while(lo<hi){ m1 = (lo+hi)/2; if(hi-lo == 1) m1++; int ccyc = cyc[m1]; int tra = (t/ccyc) * ccyc; tra -= m1; if(tra < l){ hi = m1-1; } else if(tra > l){ lo = m1; } else{ lo = m1; hi = m1; } } m1 = lo; if(m1 == 0 && t<l){ m1--; } lo = 0; hi = n; int m2 = lo; while(lo<hi){ m2 = (lo+hi)/2; if(hi-lo == 1) m2++; int ccyc = cyc[m2]; int tra = (t/ccyc) * ccyc; tra -= m2; if(tra <= r){ hi = m2-1; } else{ lo = m2; } } m2 = lo; if(m2 == 0 && t<=r){ m2--; } cout << m1-m2 << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...