Submission #1099206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099206		Pekiban	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	238 ms	27476 KiB

worst_reporter3

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    int d[n+1];
    for (int i = 1; i <= n; ++i) {
        cin >> d[i];
    }
    ll a[n+1], mn[60], mx[60], c = 0; a[0] = 1;
    fill(mn, mn + 60, 1e18);
    fill(mx, mx + 60, 1e18); mx[0   ] = mn[0] = 0;
    for (int i = 1; i <= n; ++i) {
        a[i] = ((d[i] + a[i-1] - 1) / a[i-1]) * a[i-1];
        if (a[i] != a[i-1]) {
            mn[++c] = i;
        }
        mx[c] = i;
    }
    auto calc = [&](int t, int r) {
        int x = 0;
        for (int i = 0; i <= c; ++i)    x += max(0LL, mx[i] - max(mn[i], (t / a[mn[i]]) * a[mn[i]] - r) + 1);
        return x;
    };
    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        cout << calc(t, r) - calc(t, l-1) << '\n';
    }
}

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