Submission #1088986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088986		DobromirAngelov	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	345 ms	23492 KiB

worst_reporter3

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

const int MAXN=5e5+5;
const int MAXQ=5e5+5;

int n,q;
unsigned int v[MAXN];

int getPos(int ind,int t)
{
    return (t/v[ind])*v[ind]-ind;
}

int bs(int x,int t)
{
    int l=0,r=n;
    while(l<r)
    {
        int mid=(l+r+1)/2;
        if(getPos(mid,t)>=x) l=mid;
        else r=mid-1;
    }
    return l;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>v[i];

    for(int i=2;i<=n;i++)
    {
        v[i]=((v[i]+v[i-1]-1)/v[i-1])*v[i-1];
    }

    for(int i=0;i<q;i++)
    {
        int t,l,r;
        cin>>t>>l>>r;

        int ind1=bs(r+1,t);
        int ind2=bs(l,t);
        int ans=0;
        if(l<=t && t<=r) ans++;
        ans+=ind2-ind1;
        cout<<ans<<endl;
    }

    return 0;
}

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