Submission #44994

#	Time	Username	Problem	Language	Result	Execution time	Memory
44994		SpaimaCarpatilor	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	1054 ms	262144 KiB

worst_reporter3

#include<bits/stdc++.h>

using namespace std;

int N, M, D[500009], t[500009];
const int INF = 1e9 + 5;

int getPos (int T, int i)
{
    int times = T / t[i];
    if (1LL * times * D[i] - i > INF) return INF;
    return -i + times * D[i];
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d", &N, &M), D[0] = 1, t[0] = 1;
for (int i=1; i<=N; i++)
{
    scanf ("%d", &D[i]);
    int k = D[i] / D[i - 1];
    if (D[i] % D[i - 1] != 0) k ++;
    D[i] = k * D[i - 1];
    if (k <= INF / t[i - 1]) t[i] = k * t[i - 1];
    else t[i] = INF;
}

while (M --)
{
    int T, L, R, p = 0, u = N, l = -1, r = -1;
    scanf ("%d %d %d", &T, &L, &R);
    while (p <= u)
    {
        int mij = (p + u) >> 1;
        if (getPos (T, N - mij) <= R) r = mij, p = mij + 1;
        else u = mij - 1;
    }
    if (r == -1)
    {
        printf ("0\n");
        continue;
    }
    p = 0, u = r;
    while (p <= u)
    {
        int mij = (p + u) >> 1;
        if (getPos (T, N - mij) >= L) l = mij, u = mij - 1;
        else p = mij + 1;
    }
    if (l == -1 || l > r) printf ("0\n");
    else printf ("%d\n", r - l + 1);
}
return 0;
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:20:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %d", &N, &M), D[0] = 1, t[0] = 1;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
worst_reporter3.cpp:23:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &D[i]);
     ~~~~~~^~~~~~~~~~~~~
worst_reporter3.cpp:34:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d %d", &T, &L, &R);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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