Submission #1164447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164447		fzyzzz_z	Worst Reporter 3 (JOI18_worst_reporter3)	C++20	100 / 100	355 ms	15180 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q; 
    cin >> n >> q; 
    vector<ll> d(n + 1);    
    for (int i = 1; i <= n; ++i) {
        cin >> d[i]; 
    }

    vector<ll> dist(n + 1), time(n + 1); 
    dist[0] = 1; 
    time[0] = 1; 

    for (int i = 1; i <= n; ++i) {
        // if (dist[i - 1] >= d[i]) {
        //     dist[i] = dist[i - 1]; 
        //     time[i] = time[i - 1]; 
        //     continue; 
        // }

        ll need = (d[i] + dist[i - 1] - 1) / dist[i - 1]; 
        dist[i] = dist[i - 1] * need; 
        time[i] = time[i - 1] * need; 

        // cout << dist[i] << " " << time[i] << "\n";
    }


    auto calc_pos = [&] (int p, ll t) -> ll {
        ll st = -p; 
        ll moves = t / time[p]; 
        st += moves * dist[p]; 

        return st; 
    }; 

    while (q--) {
        ll t, l, r; 
        cin >> t >> l >> r; 

        if (calc_pos(0, t) < l || r < calc_pos(n, t)) {
            cout << 0 << '\n'; 
            continue; 
        }

        int f, s; 
        int lo = 0, hi = n; 
        while (lo < hi) {
            int md = (lo + hi) / 2; 
            if (calc_pos(md, t) <= r) {
                hi = md; 
            } else {
                lo = md + 1; 
            }
        }
        f = lo; 
        lo = 0, hi = n; 
        while (lo < hi) {
            int md = (lo + hi + 1) / 2; 
            if (calc_pos(md, t) >= l) {
                lo = md; 
            } else {
                hi = md - 1; 
            }
        }
        s = lo; 

        // cout << f << ' ' << s << '\n'; 

        cout << (s >= f ? s - f + 1 : 0) << "\n"; 
    }



    return 0;
}

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