Submission #797922

#	Time	Username	Problem	Language	Result	Execution time	Memory
797922		vjudge1	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	444 ms	26980 KiB

worst_reporter3

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const ll N = 5e5 ;
ll n, q, tn, d[N + 1], ans[N + 1], pref[N + 1] ;
struct query
{
    ll t, l, r, ind ;
};
vector<query> qr ;
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n >> q ;
    for(ll i = 1 ; i <= n ; i++)
        cin >> d[i] ;
    for(ll i = 1 ; i <= q ; i++)
    {
        query q ;
        cin >> q.t >> q.l >> q.r ;
        q.ind = i ;
        qr.push_back(q) ;
    }
    pref[1] = d[1] ;
    for(ll i = 2 ; i <= n ; i++)
    {
        ll l = 0, r = 1e9 + 1 ;
        while(l + 1 < r)
        {
            ll mid = (l + r) >> 1ll ;
            if(mid * pref[i - 1] >= d[i])r = mid ;
            else l = mid ;
        }
        pref[i] = pref[i - 1] * r ;
    }
    for(query i : qr)
    {
        ll l1 = 0, r1 = n + 1, l2 = 0, r2 = n + 1 ;
        while(l1 + 1 < r1)
        {
            ll mid = (l1 + r1) >> 1ll, posmd = (i.t / pref[mid]) * pref[mid] - mid ;
            if(posmd <= i.r)r1 = mid ;
            else l1 = mid ;
        }
        while(l2 + 1 < r2)
        {
            ll mid = (l2 + r2) >> 1ll, posmd = (i.t / pref[mid]) * pref[mid] - mid ;
            if(posmd >= i.l)l2 = mid ;
            else r2 = mid ;
        }
        cout << l2 - r1 + 1 + (i.l <= i.t && i.t <= i.r) << '\n' ;
//        cout << "\n" ;
    }
    return 0 ;
}
//4 5
//1
//1
//1
//1
//2 1 4
//1 3 6
//20 17 19
//20 17 18
//20 0 20
//1 0 -1 -2 -3
//2 1 0 -1 -2
//3 2 1 0 -1
//4 3 2 1 0
//5 4 3 2 1
//6 5 4 3 2
//7 6 5 4 3
//8 7 6 5 4
//9 8 7 6 5
//10 9 8 7 6
//11 10 9 8 7
//12 11 10 9 8
//13 12 11 10 9
//14 13 12 11 10
//15 14 13 12 11
//16 15 14 13 12
//17 16 15 14 13
//18 17 16 15 14
//19 18 17 16 15
//20 19 18 17 16

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