Submission #679104

#	Time	Username	Problem	Language	Result	Execution time	Memory
679104		Ronin13	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	577 ms	33356 KiB

worst_reporter3

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 2e5 + 1;


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    int q; cin >> q;
    ll t[n + 1], d[n + 1], x[n + 1];
    t[0] = 1, x[0] = 1;
    for(int i = 1; i <= n; i++)
        cin >> d[i];
    for(int i = 1; i <= n; i++){
        if(d[i] < x[i - 1]) x[i] = x[i - 1], t[i] = t[i - 1];
        else{
            ll v = (d[i] + x[i - 1] - 1) / x[i - 1];
            t[i] = t[i - 1] * v;
            x[i] = v * x[i - 1];
        }
    }
    /*for(int i= 1; i <= n; i++){
        cout << x[i] << ' '  << t[i] << "\n";
    }*/
    while(q--){
        ll T, L, R; cin >> T >> L >> R;
        ll l = -1, r = n + 1;
        while(l + 1 < r){
            ll mid = (l + r) / 2;
            ll u = T / t[mid];
            if(-mid + x[mid] * u >=L) l = mid;
            else r = mid;
        }
        int X = l;
        l = -1, r = n + 1;
        while(l + 1 < r){
            ll mid = (l + r) / 2;
            ll u = T / t[mid];
            if(-mid + x[mid] * u <= R) r = mid;
            else l = mid;
        }
        cout << max((int)X - (int)r + 1, 0) << "\n";
    }
    return 0;
}

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