Submission #114122

#	Time	Username	Problem	Language	Result	Execution time	Memory
114122		shayan_p	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	999 ms	25560 KiB

worst_reporter3

// High above the clouds there is a rainbow...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=5e5+10,mod=1e9+7;
const ll inf=1e18;

ll dp[maxn];

int f(ll a,ll b,ll c,ll d){
    ll A=max(a,c),B=min(b,d);
    return max(int(0),int(B-A));
}
int fnd(int r,ll x){
    int l=0; r++;
    while(r-l>1){
	int mid=(l+r)>>1;
	if(x>=dp[mid]) l=mid;
	else r=mid;
    }
    return l;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++)
	cin>>dp[i];
    dp[0]=1;
    for(int i=1;i<=n;i++)
	dp[i]=((dp[i]+dp[i-1]-1)/dp[i-1])*dp[i-1];
    while(q--){
	ll t,l,r,pos=-n,ans=0;cin>>t>>l>>r;
	int pt=n;
	while(t){
	    int start=pos;
	    int pt2=fnd(pt,t);
	    pos+=pt-pt2, pt=pt2;
	    ans+=f(start,pos,l,r+1);
	    pos+=(t/dp[pt])*dp[pt], t%=dp[pt];
	}
	ans+=f(pos,pos+pt+1,l,r+1);
	cout<<ans<<"\n";
    }
    return 0;
}
// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn.
//  * Overflows.

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 81 / 81