Submission #618052

#	Time	Username	Problem	Language	Result	Execution time	Memory
618052		chonka	Worst Reporter 3 (JOI18_worst_reporter3)	C++98	100 / 100	618 ms	29380 KiB

worst_reporter3

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MAXN = 5e5 + 7 ;
const int inf = 1e9 + 7 ;
int n , q ;
ll d[ MAXN ] , hh[ MAXN ] ;


ll eval ( int i , int t ) {
    if ( i == 0 ) { return t ; }
    ll lst = ( t / hh[ i ] ) * hh[ i ] ;
    return lst - i ;
}

int f ( int mn , int t ) {
    int l , r , mid ;
    if ( eval ( 0 , t ) < mn ) { return 0 ; }
    if ( eval ( n , t ) >= mn ) { return n + 1 ; }
    l = 0 , r = n ;
    while ( r - l > 3 ) {
        mid = ( l + r ) / 2 ;
        if ( eval ( mid , t ) >= mn ) { l = mid ; }
        else { r = mid - 1 ; }
    }
    while ( eval ( r , t ) < mn ) { -- r ; }
    return ( r + 1 ) ;
}

void solve ( ) {
    cin >> n >> q ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> d[ i ] ;
    }
    hh[ 1 ] = d[ 1 ] ;
    for ( int i = 2 ; i <= n ; ++ i ) {
        ll l , r , mid ;
        l = 0 , r = inf ;
        while ( r - l > 3 ) {
            mid = ( l + r ) / 2 ;
            if ( -i + d[ i ] < eval ( i - 1 , mid ) ) { r = mid ; }
            else { l = mid ; }
        }
        while ( l < inf && -i + d[ i ] >= eval ( i - 1 , l ) ) { ++ l ; }
        hh[ i ] = l ;
    }
    while ( q -- ) {
        int st , en , t ;
        cin >> t >> st >> en ;
        cout << f ( st , t ) - f ( en + 1 , t ) << "\n" ;
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

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