Submission #482499

#	Time	Username	Problem	Language	Result	Execution time	Memory
482499		Rainbowbunny	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	510 ms	25412 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;

int n, q;
long long d[MAXN];

long long Get(long long id, long long t)
{
    long long k = t / d[id];
    return -id + d[id] * k;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    d[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        cin >> d[i];
        long long g = (d[i] + d[i - 1] - 1) / d[i - 1] * d[i - 1];
        d[i] = g;
    }
    while(q--)
    {
        long long t, l, r;
        cin >> t >> l >> r;
        long long ll = 0, rr = n;
        while(ll < rr)
        {
            long long mid = (ll + rr) >> 1;
            if(Get(mid, t) > r)
            {
                ll = mid + 1;
            }
            else
            {
                rr = mid;
            }
        }
        if(Get(ll, t) > r)
        {
            cout << 0 << '\n';
        }
        else
        {
            if(Get(ll, t) < l)
            {
                cout << 0 << '\n';
            }
            else
            {
                long long l2 = ll, r2 = n;
                while(l2 < r2)
                {
                    long long mid = (l2 + r2 + 1) >> 1;
                    if(Get(mid, t) < l)
                    {
                        r2 = mid - 1;
                    }
                    else
                    {
                        l2 = mid;
                    }
                }
                cout << (l2 - ll + 1) << '\n';
            }
        }
    }
}

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