Submission #987776

#	Time	Username	Problem	Language	Result	Execution time	Memory
987776		alextodoran	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	462 ms	27588 KiB

worst_reporter3

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 500000;

int N, Q;
int D[N_MAX + 2];

ll F[N_MAX + 2];

ll get_pos (int t, int i) {
    return (t / F[i]) * F[i] - i;
}

int cnt_after (int t, int x) {
    int l = -1, r = N;
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (get_pos(t, mid) >= x) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l + 1;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> Q;
    F[0] = 1;
    for (int i = 1; i <= N; i++) {
        cin >> D[i];
        F[i] = F[i - 1] * ((D[i] + F[i - 1] - 1) / F[i - 1]);
    }
    while (Q--) {
        int t, l, r;
        cin >> t >> l >> r;
        cout << cnt_after(t, l) - cnt_after(t, r + 1) << "\n";
    }

    return 0;
}

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