Submission #602834

#	Time	Username	Problem	Language	Result	Execution time	Memory
602834		elkernos	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	573 ms	29252 KiB

worst_reporter3

#include <bits/stdc++.h>

using namespace std;

#define int long long

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    cin >> n >> q;
    vector<int> d(n + 1), f(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> d[i];
        if(i == 1) {
            f[i] = d[i];
        }
        else {
            f[i] = (d[i] + f[i - 1] - 1) / f[i - 1] * f[i - 1];
        }
    }
    auto licz = [&](int t, int x) {
        int lo = 1, hi = n, ans = 0;
        while(lo <= hi) {
            int mid = (lo + hi) / 2;
            if(t / f[mid] * f[mid] - mid >= x) {
                lo = mid + 1;
                ans = mid;
            }
            else {
                hi = mid - 1;
            }
        }
        return ans;
    };
    for(int i = 1; i <= q; i++) {
        int t, l, r;
        cin >> t >> l >> r;
        cout << licz(t, l) - licz(t, r + 1) + (l <= t && t <= r) << '\n';
    }
}

// (0, 0), (1, 1), (2, 2), (3, 3), (4, 4), ...
// (-1, 0), (d_1 - 1, d_1), (2 * d_1 - 1, 2 * d_1), ...
// (-2, 0), ()

// k*d_1 - 1 >= -2 + d_2 - 1

// k >= d_2/d_1
// (k * ceil(d_2, d_1) * d_1 - 2)

//...

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