Submission #242207

#	Time	Username	Problem	Language	Result	Execution time	Memory
242207		cheeheng	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	734 ms	11308 KiB

worst_reporter3

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

long long D[500005];
long long lag[500005];

bool boleh(int i, long long T, long long X){
    long long pos = -i + T/lag[i]*lag[i];
    //printf("boleh(%d, %lld, %lld): %lld\n", i, T, X, pos);
    return pos <= X;
}

int N, Q;
int numAtMost(long long T, long long X){
    int lo = 0;
    if(!boleh(N, T, X)){
        return 0;
    }
    int hi = N;
    while(lo < hi){
        int mid = (lo+hi)>>1;
        if(boleh(mid, T, X)){
            hi = mid;
        }else{
            lo = mid+1;
        }
    }
    return N-lo+1;
}

int main(){
    scanf("%d%d", &N, &Q);

    for(int i = 1; i <= N; i ++){
        scanf("%lld", &D[i]);
    }

    lag[0] = 1;
    for(int i = 1; i <= N; i ++){
        lag[i] = (1+(D[i]-1)/lag[i-1]) * lag[i-1];
        //printf("lag[%d]=%lld\n", i, lag[i]);
    }

    while(Q --){
        long long T, L, R;
        scanf("%lld%lld%lld", &T, &L, &R);

        for(int i = 0; i <= N; i++){
            boleh(i, T, 1);
        }
        //printf("next part\n");

        int temp1 = numAtMost(T, L-1);
        int temp2 = numAtMost(T, R);
        //printf("%d %d\n", temp1, temp2);
        printf("%d\n", temp2-temp1);
    }

    return 0;
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:32: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:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &D[i]);
         ~~~~~^~~~~~~~~~~~~~~
worst_reporter3.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld", &T, &L, &R);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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