Submission #225191

#TimeUsernameProblemLanguageResultExecution timeMemory
225191kshitij_sodaniWorst Reporter 3 (JOI18_worst_reporter3)C++17
100 / 100
1580 ms25856 KiB
#include <iostream> #include <bits/stdc++.h> using namespace std; #define pb push_back typedef long long llo; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); llo n,q; llo aa; cin>>n>>q; vector<llo> bb; bb.pb(1); for(llo i=0;i<n;i++){ cin>>aa; llo cc=bb[bb.size()-1]; llo dd=(aa/cc)*cc; if(aa%cc>0){ dd+=cc; } bb.pb(dd); // cout<<dd<<" "; } // cout<<endl; llo tt,l,r; while(q--){ cin>>tt>>l>>r; if(tt<l){ cout<<0<<endl; continue; } llo ma=tt-tt%bb[bb.size()-1]-(bb.size()); if(ma>r){ cout<<0<<endl; continue; } llo low=0; llo high=bb.size()-1; while(low<high-1){ llo mid=(low+high)/2; llo val=tt-tt%bb[mid]-mid; if(val<l){ high=mid; } else{ low=mid; } } llo ind2; llo val2=tt-tt%bb[high]-high; //cout<<low<<" "<<high<<" "<<val2<<endl; if(val2<l){ ind2=low; } else{ ind2=high; } low=0; high=bb.size()-1; while(low<high-1){ llo mid=(low+high)/2; llo val=tt-tt%bb[mid]-mid; if(val>r){ low=mid; } else{ high=mid; } } llo ind3; llo val3=tt-tt%bb[low]-low; if(val3>r){ ind3=high; } else{ ind3=low; } // cout<<ind3<<" "<<ind2<<endl; cout<<ind2-ind3+1<<endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...