Submission #113282

#	Time	Username	Problem	Language	Result	Execution time	Memory
113282		popovicirobert	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	841 ms	27456 KiB

worst_reporter3

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int INF = 2e9;

inline int get(int pos, vector <ll> &prd, int t) {
    return (t / prd[pos]) * prd[pos];
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, q;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> q;

    vector <int> d(n + 1, 1);

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

    vector <ll> prd(n + 1, 1);

    for(i = 1; i <= n; i++) {
        prd[i] = (d[i] + prd[i - 1] - 1) / prd[i - 1];
        prd[i] *= prd[i - 1];

        if(prd[i] > INF) {
            prd[i] = INF;
        }
        //cerr << prd[i] << " ";
    }


    while(q > 0) {
        q--;

        int t, l, r;
        cin >> t >> l >> r;

        int a = 0, b = 0;

        for(int step = 1 << 19; step; step >>= 1) {
            if(a + step <= n && -(a + step) + get(a + step, prd, t) > r) {
                a += step;
            }
            if(b + step <= n && -(b + step) + get(b + step, prd, t) >= l) {
                b += step;
            }
        }

        int ans = b - a;

        if(l <= t && t <= r) {
            ans++;
        }

        cout << ans << "\n";

    }

    //cin.close();
    //cout.close();
    return 0;
}

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