Submission #159963

#	Time	Username	Problem	Language	Result	Execution time	Memory
159963		combi1k1	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	931 ms	25496 KiB

worst_reporter3

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int   N   = 5e5 + 5;

int d[N];
int n, q;

int get(int T,int P)    {
    int l = 0;
    int r = n + 1;
    for(; l < r ;)  {
        int m = (l + r) / 2;

        if (T / d[m] * d[m] < P + m)
            r = m;
        else
            l = m + 1;
    }
    return  l;
}

signed main()   {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> q;

    d[0] = 1;

    for(int i = 1 ; i <= n ; ++i)   {
        int x;  cin >> x;
        int k = (d[i - 1] + x - 1) / d[i - 1];
        d[i] = k * d[i - 1];
    }

    for(int i = 1 ; i <= q ; ++i)   {
        int T;  cin >> T;
        int l;  cin >> l;
        int r;  cin >> r;

        cout << get(T,l) - get(T,r + 1) << "\n";
    }
}
/*
3 6
2
5
3
1 2 4
2 2 4
3 2 4
4 2 4
5 2 4
6 2 4
*/

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