Submission #211010

#	Time	Username	Problem	Language	Result	Execution time	Memory
211010		DodgeBallMan	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	890 ms	29464 KiB

worst_reporter3

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

const int N = 5e5 + 10;
int n, q;
long d[N], t[N];

long chk( long x, long ti ) { return ( ti/t[x] ) * t[x] - x; }
int main()
{
    scanf("%d %d",&n,&q);
    d[0] = 1, t[0] = 1;
    for( int i = 1 ; i <= n ; i++ ) scanf("%lld",&d[i]);
    //printf("\n");
    for( int i = 1 ; i <= n ; i++ ) {
        long a = d[i] / t[i-1];
        if( a*t[i-1] != d[i] ) a++;
        t[i] = t[i-1] * a;
        //printf("%lld\n",t[i]);
    }
    while( q-- ) {
        long ti, le, ri, lb, rb;
        scanf("%lld %lld %lld",&ti,&le,&ri);
        int l = 0, r = n;
        if( chk( 0, ti  ) < le ) {
            printf("0\n");
            continue ;
        }
        else if( chk( n, ti ) > ri ) {
            printf("0\n");
            continue ;
        }
        while( l < r ) {
            long mid = ( long )( l + r >> 1 );
            if( chk( mid, ti ) <= ri ) r = mid;
            else l = mid + 1;
        }
        rb = ( long )l, l = 0, r = n;
        while( l < r ) {
            long mid = ( long )( l + r + 1 >> 1 );
            if( chk( mid, ti ) >= le ) l = mid;
            else r = mid - 1;
        }
        lb = ( long )l;
        //printf("%lld %lld\n",lb,rb);
        printf("%lld\n",lb-rb+1);
    }
    return 0;
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:35:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             long mid = ( long )( l + r >> 1 );
                                  ~~^~~
worst_reporter3.cpp:41:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             long mid = ( long )( l + r + 1 >> 1 );
                                  ~~~~~~^~~
worst_reporter3.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&q);
     ~~~~~^~~~~~~~~~~~~~~
worst_reporter3.cpp:14:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for( int i = 1 ; i <= n ; i++ ) scanf("%lld",&d[i]);
                                     ~~~~~^~~~~~~~~~~~~~
worst_reporter3.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld",&ti,&le,&ri);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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