Submission #242209

#	Time	Username	Problem	Language	Result	Execution time	Memory
242209		dantoh000	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	705 ms	7544 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q;
int d[500005];
int s[500005];
int POS(int id, int t){
    return (t/s[id])*s[id]-id;
}
int main(){
    scanf("%d%d",&n,&q);
    s[0] = 1;
    for (int i =1;  i <=n; i++) scanf("%d",&d[i]);
    for (int i =1;  i <=n; i++){
        int ct = (d[i]-1)/s[i-1]+1;
        //printf("after %d of prev jumps, %d jumps\n",ct,i);
        s[i] = s[i-1]*ct;
    }
    /*for (int i = 1; i <= n; i++){
        printf("%d: %d\n",i,s[i]);
    }*/
    for (int i = 1; i <= q; i++){
        int t,l,r;
        scanf("%d%d%d",&t,&l,&r);
        int Llo = 0, Lhi = n;
        int Rlo = 0, Rhi = n;
        while (Llo < Lhi){
            int mid = (Llo+Lhi+1)/2;
            if (POS(mid,t) < l){
                Lhi = mid-1;
            }
            else{
                Llo = mid;
            }
        }
        while (Rlo < Rhi){
            int mid = (Rlo+Rhi)/2;
            if (POS(mid,t) > r){
                Rlo = mid+1;
            }
            else{
                Rhi = mid;
            }
        }
        int ans = Llo-Rlo+1;
        if (Llo == 0 && Rlo == 0){
            int pos = POS(0,t);
            if (l <= pos && pos <= r) ans = 1;
            else ans = 0;
        }
        if (Llo == n && Rlo == n){
            int pos = POS(n,t);
            if (l <= pos && pos <= r) ans = 1;
            else ans = 0;
        }
        printf("%d\n",ans);
        //printf("<%d,%d> = %d\n",Llo, Rlo,ans);
    }

}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:11: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:13:38: 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("%d",&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("%d%d%d",&t,&l,&r);
         ~~~~~^~~~~~~~~~~~~~~~~~~

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