Submission #1322430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1322430		adiat	Worst Reporter 3 (JOI18_worst_reporter3)	C++20	7 / 100	1058 ms	7200 KiB

worst_reporter3

#include<bits/stdc++.h>
#define int long long
using namespace std;
int bs(vector<int> &a, int n, int l, int r)
{
    int res=-1;
    int i=0,j=n-1;
    while(i<=j)
    {
        int mid=(i+j)/2;
        if(r-(r%a[mid])-mid-1>=l)
        {
            res=mid;
            i=mid+1;
        }
        else
        {
            j=mid-1;
        }
    }
    return res;
}
signed main()
{
    int n,q;
    cin>>n;
    cin>>q;
    vector<int> a(n);
    for(int &i: a) cin>>i;
    for(int i=1; i<n; i++)
    {
        int x=a[i-1];
        if(a[i]<=a[i-1]) a[i]=x;
        else a[i]=a[i]+x-a[i]%x;
    }
    // for(int i: a) cout<<i<<" ";
    while(q--)
    {
        int t,l,r;
        cin>>t>>l>>r;
        int ans=0, y=0,x;
        if(t<l) ans=0;
        else if(t==l) ans=1;
        else if(t>l && t<=r)
        {
            ans=1;
            r=t;
            x=bs(a, n, l, r);
            ans+=x-y+1;
        }
        else
        {
            y=bs(a, n, r+1, t);
            x=bs(a, n, l, t);
            // cout<<x<<y<<" ";
            ans+=x-y;
        }
        cout<<ans<<endl;
    }

}

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