oj.uz

Submission #437956

# Submission time Handle Problem Language Result Execution time Memory
437956 2021-06-27T10:38:56 Z blue Worst Reporter 3 (JOI18_worst_reporter3) C++17
12 / 100
 2000 ms 25124 KB 
#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 T[i] seconds.
*/
const int maxN = 500000;

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

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

int main()
{
    int N, Q;
    cin >> N >> Q;

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

    JT[0] = 1;
    J[0] = 1;

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

        // 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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2054 ms 25124 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 5 ms 288 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2054 ms 25124 KB Time limit exceeded
2 Halted 0 ms 0 KB -