Submission #242206

#	Time	Username	Problem	Language	Result	Execution time	Memory
242206		tqbfjotld	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	734 ms	6136 KiB

worst_reporter3

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

int n,q;
int arr[500005];

int func(int t, int person){
    if (person==-1) return t;
    if (person==-2) return 1000000005;
    return (t/arr[person])*arr[person]-person-1;
}

int main(){
    scanf("%d%d",&n,&q);
    for (int x = 0; x<n; x++){
        scanf("%d",&arr[x]);
    }
    for (int x = 1; x<n; x++){
        arr[x] = ((arr[x]-1)/arr[x-1])*arr[x-1]+arr[x-1];
    }
    for (int x = 0; x<q; x++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        int lb,rb;
        if (func(a,-1)<b){
            printf("0\n");
            continue;
        }
        if (func(a,n-1)>c){
            printf("0\n");
            continue;
        }
        int l = -1;
        int r = n;
        while (l+1<r){
            int mid = (l+r)/2;
            if (func(a,mid)>=b){
                l = mid;
            }
            else r = mid;
        }
        lb = l;

        l = -2;
        r = n-1;
        while (l+1<r){
            int mid = (l+r)/2;
            //printf("func mid %d\n",func(a,mid));
            if (func(a,mid)<=c){
                r = mid;
            }
            else{
                l = mid;
            }
        }
        rb = r;

        //printf("func(rb): %d\n",func(a,rb));
        printf("%d\n",lb-rb+1);
        //printf("%d %d\n",lb,rb);

    }
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:14: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:16:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[x]);
         ~~~~~^~~~~~~~~~~~~~
worst_reporter3.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&a,&b,&c);
         ~~~~~^~~~~~~~~~~~~~~~~~~

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