Submission #281733

#	Time	Username	Problem	Language	Result	Execution time	Memory
281733		MKopchev	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	953 ms	27408 KiB

worst_reporter3

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

const int nmax=5e5+42,inf=1e9+42;

int n,q;

int inp[nmax];

long long help[nmax];

int score(int i,int t)
{
    return (t/help[i])*help[i]-i;
}
int last_valid(int pos,int t)
{
    int ok=n+1,not_ok=-1;

    while(ok-not_ok>1)
    {
        int av=(ok+not_ok)/2;

        if(score(av,t)<=pos)ok=av;
        else not_ok=av;
    }

    //cout<<"last "<<ok<<endl;

    return ok;
}

int first_valid(int pos,int t)
{
    int ok=-1,not_ok=n+1;

    while(not_ok-ok>1)
    {
        int av=(ok+not_ok)/2;

        if(score(av,t)>=pos)ok=av;
        else not_ok=av;
    }

    //cout<<"first "<<ok<<endl;

    return ok;
}
int main()
{
    scanf("%i%i",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%i",&inp[i]);
    }
    inp[0]=1;
    help[0]=1;

    for(int i=1;i<=n;i++)
    {
        help[i]=help[i-1]*((inp[i]+help[i-1]-1)/help[i-1]);

        if(help[i]>inf)help[i]=inf;

        //cout<<i<<" -> "<<help[i]<<endl;
    }

    for(int i=1;i<=q;i++)
    {
        int l,r,t;

        scanf("%i%i%i",&t,&l,&r);
        /*
        for(int j=0;j<=n;j++)
            cout<<j<<" -> "<<score(j,t)<<endl;
        */

        printf("%i\n",first_valid(l,t)-last_valid(r,t)+1);
    }
    return 0;
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |     scanf("%i%i",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~
worst_reporter3.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |         scanf("%i",&inp[i]);
      |         ~~~~~^~~~~~~~~~~~~~
worst_reporter3.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |         scanf("%i%i%i",&t,&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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