Submission #997917

#	Time	Username	Problem	Language	Result	Execution time	Memory
997917		juliany2	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	543 ms	29264 KiB

worst_reporter3

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int N = 5e5 + 7;
int n, q;
ll d[N], c[N];

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

    cin >> n >> q;

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

        c[i] = (d[i] + c[i - 1] - 1) / c[i - 1] * c[i - 1];
    }

    auto query = [&](ll t, ll x) {
        ll res = n + 1, shift = 0;;

        while (t > 0) {
            int i = upper_bound(c, c + n + 1, t) - c - 1;

            ll dist = t - (t % c[i]);
            t -= dist, shift += dist;

            res = min(res, n + 1 - i + max(x - (shift - i), -1LL));
        }

        return res;
    };

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

        cout << query(t, r) - query(t, l - 1) << '\n';
    }

    return 0;
}

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