Submission #437958

#	Time	Username	Problem	Language	Result	Execution time	Memory
437958		blue	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	861 ms	27252 KiB

worst_reporter3

#include <iostream>
using namespace std;

/*
Let P(i, t) be the position of the person i at the time t

P(0, t) = t
P(1, t) = -1 + P(0, t)

Every contestant i jumps J[i] units to the right every J[i] seconds.
*/
const int maxN = 500000;

int N, Q;
int D[1+maxN];
long long J[1+maxN]; //jump distance/time

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

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

    int N, Q;
    cin >> N >> Q;

    for(int i = 1; i <= N; i++) cin >> D[i];

    J[0] = 1;

    for(int i = 1; i <= N; i++)
    {
        J[i] = min(((D[i] / J[i-1]) + bool(D[i] % J[i-1])) * J[i-1], 1'000'000'001LL);
        // cerr << "JT[" << i << "] = " << JT[i] << ", J[" << i << "] = " << J[i] << '\n';
    }

    for(int j = 1; j <= Q; j++)
    {
        long long T, L, R;
        cin >> T >> L >> R;

        // for(int i = 0; i <= N; i++) cerr << loc(i, T) << ' ';
        // cerr << '\n';

        int rm = -1;
        for(int bit = 20; bit >= 0; bit--)
        {
            int p = rm + (1 << bit);
            if(p > N) continue;
            if(loc(p, T) <= R) continue;
            rm = p;
        }
        rm++;

        if(rm > N || loc(rm, T) < L || R < loc(rm, T))
        {
            cout << 0 << '\n';
            continue;
        }

        int lm = -1;
        for(int bit = 20; bit >= 0; bit--)
        {
            int p = lm + (1 << bit);
            if(p > N) continue;
            if(L <= loc(p, T)) lm = p;
        }

        cout << lm-rm+1 << '\n';
    }
}

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