Submission #627076

#TimeUsernameProblemLanguageResultExecution timeMemory
627076codr0Worst Reporter 3 (JOI18_worst_reporter3)C++14
100 / 100
583 ms7280 KiB
// Code by Parsa Eslami #include <bits/stdc++.h> #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define err(x) cerr<#x<<" : "<<x<<'\n' #define FOR(i,a,b) for(int i=a;i<=b;i++) #define FORR(i,a,b) for(int i=a;i>=b;i--) #define F first #define S second #define pb push_back #define bit(i,j) ((j>>i)&1) #define maxm(a,b) a=max(a,b) #define minm(a,b) a=min(a,b) #define all(x) x.begin(),x.end() #define SZ(x) (int)x.size() #define dmid int mid=(r+l)/2 #define lc 2*id #define rc 2*id+1 using namespace std; const int N=5e5+4; int r[N],d[N]; int n; int pos(int x,int t){ return (-x+(t/r[x])*d[x]); } int32_t main(){ iostream::sync_with_stdio(0); cin.tie(0); int q; cin>>n>>q; d[0]=1; r[0]=1; FOR(i,1,n) cin>>d[i]; FOR(i,1,n){ if(r[i-1]>1e9){ r[i]=2e9; continue;} /*if(d[i-1]==0){ cout<<i<<'\n'; FOR(j,0,i) cout<<d[j]<<" "; cout<<'\n'; exit(0); }*/ ll x=d[i]/d[i-1]; if(d[i]%d[i-1]!=0) x++; /*if(x==0){ cout<<i<<"&\n"; }*/ d[i]=x*d[i-1]; x=x*r[i-1]; if(x>1e9) r[i]=2e9; else r[i]=x; } /*FOR(i,0,n) cout<<r[i]<<" "; cout<<'\n'; FOR(i,0,n) cout<<d[i]<<" "; cout<<'\n';*/ FOR(i,1,q){ int t,l,rr; cin>>t>>l>>rr; int ans=0; int L=-1,R=n+1; while(R-L>1){ int mid=(R+L)/2; if(pos(mid,t)<=rr) R=mid; else L=mid; } ans+=(n+1-R); L=-1,R=n+1; while(R-L>1){ int mid=(R+L)/2; if(pos(mid,t)<l) R=mid; else L=mid; } ans-=(n+1-R); cout<<ans<<'\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...