Submission #253028

#TimeUsernameProblemLanguageResultExecution timeMemory
253028wwddWorst Reporter 3 (JOI18_worst_reporter3)C++14
100 / 100
650 ms29692 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> vl; vl w,x; int main() { ios::sync_with_stdio(0);cin.tie(0); int n,q; cin >> n >> q; for(int i=0;i<n;i++) { ll t; cin >> t; w.push_back(t); } ll pm = 1; x.push_back(pm); for(int i=0;i<n;i++) { pm = (w[i]+pm-1)/pm*pm; x.push_back(pm); } while(q--) { ll ti,l,r; cin >> ti >> l >> r; ll st = 0,ed = x.size()-1; ll la = -1; while(st <= ed) { ll m = (st+ed)/2; ll po = (ti/x[m]*x[m])-m; if(po >= l) { la = m; st = m+1; } else { ed = m-1; } } st = 0;ed = x.size()-1; ll lb = -1; while(st <= ed) { ll m = (st+ed)/2; ll po = (ti/x[m]*x[m])-m; if(po > r) { lb = m; st = m+1; } else { ed = m-1; } } cout << la-lb << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...