Submission #1240268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240268		duckindog	Worst Reporter 3 (JOI18_worst_reporter3)	C++20	100 / 100	341 ms	15056 KiB

worst_reporter3

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 500'000 + 10;
int n, q;
int d[N];

pair<int, int> vel[N];

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0); 

    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> d[i];

    vel[0] = {1, 1};
    for (int i = 1; i <= n; ++i) { 
        const auto& [t1, dist1] = vel[i - 1];
        int le = 1, ri = 1'000'000'000, it = -1;
        while (le <= ri) { 
            int mid = (le + ri) >> 1;
            if (dist1 * mid >= d[i]) ri = mid - 1, it = mid;
            else le = mid + 1;
        }
        vel[i] = make_pair(t1 * it, dist1 * it);
    }

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

        int lt = -1;
        { // binsearch lt
            int le = 0, ri = n;
            while (le <= ri) { 
                int mid = (le + ri) >> 1;
                int dist = (t / vel[mid].first * vel[mid].second - mid);
                if (dist > r) le = mid + 1;
                else if (dist < l) ri = mid - 1;
                else ri = mid - 1, lt = mid;
            }
        }

        int rt = -1;
        { // binsearch rt
            int le = 0, ri = n;
            while (le <= ri) { 
                int mid = (le + ri) >> 1;
                int dist = (t / vel[mid].first * vel[mid].second - mid);
                if (dist > r) le = mid + 1;
                else if (dist < l) ri = mid - 1;
                else le = mid + 1, rt = mid;
            }
        }
        
        if (lt == -1 || rt == -1 || lt > rt) cout << 0 << "\n";
        else cout << rt - lt + 1 << "\n";
    }
}

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