제출 #797877

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
797877		vjudge1	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	1323 ms	29176 KiB

worst_reporter3

#include <bits/stdc++.h>

#define fi first
#define se second

const int N = 500500;
const int mod = 1e9 + 7;

using namespace std;

int n;
int q;
long long d[N];
long long f[N];

long long get(int i, long long t)
{
    return t / f[i] * f[i] - i;
}

int solve(long long k, long long t)
{
    int l = 0, r = n + 1;
    while (l < r) {
        int m = (l + r) / 2;
        if (get(m, t) <= k) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    return n - l + 1;
}

int main() {
    #ifdef zxc
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    cin >> n >> q;
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
        f[i] = ((d[i] - 1) / f[i - 1] + 1) * f[i - 1];
    }
    for (int i = 1; i <= q; i++) {
        long long l, r, t;
        cin >> t >> l >> r;
        cout << solve(r, t) - solve(l - 1, t) << "\n";
    }
}

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