Submission #797911

#	Time	Username	Problem	Language	Result	Execution time	Memory
797911		vjudge1	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	0 / 100	434 ms	26944 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) >> 1 ;
            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) >> 1, 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) >> 1, 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' ;
    }
    return 0 ;
}

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