Submission #855440

#	Time	Username	Problem	Language	Result	Execution time	Memory
855440		8pete8	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	435 ms	25560 KiB

worst_reporter3

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#define int long long
const int mxn=2*1e5,mod=1000000007,lg=25,root=1000,inf=1e18;
int32_t main(){
    fastio
    int n,q;cin>>n>>q;
    vector<int>v(n+1);//jump time;
    v[0]=1;
    for(int i=1;i<=n;i++){
        int d;cin>>d;
        if(i==0){
            v[i]=d;
            continue;
        }
        int tmp=ceil(d*1.0/v[i-1]);//how many times
        v[i]=v[i-1]*tmp;
    }
    while(q--){
        int ql,qr,t;cin>>t>>ql>>qr;
        int l=0,r=n,ans1=-1,ans2=inf;
        while(l<=r){
            int mid=l+(r-l)/2;
            int val=((t/v[mid])*v[mid])-mid;
            if(val>=ql){
                l=mid+1;
                ans1=max(ans1,mid);
            }
            else r=mid-1;
        }
        l=0,r=n;
        while(l<=r){
            int mid=l+(r-l)/2;
            int val=((t/v[mid])*v[mid])-mid;
            if(val<=qr){
                r=mid-1;
                ans2=min(ans2,mid);
            }
            else l=mid+1;
        }
        if(ans2==inf)cout<<0<<'\n';
        else cout<<ans1-ans2+1<<'\n';
    }
}

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