Submission #124655

#	Time	Username	Problem	Language	Result	Execution time	Memory
124655		Mtaylor	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	19 / 100	1251 ms	25180 KiB

worst_reporter3

    #include <bits/stdc++.h>
     
        using namespace std;
        typedef long long ll;
        typedef vector<ll> vl ;
     
        #define mp make_pair
        #define pb push_back
        #define f first
        #define s second
        #define all(v) (v).begin(),(v).end()
     
     
        const int MOD = 1000000007;
        const int N = 1000005;
        const double PI =4*atan(1);
        const double eps = 1e-7;
        
        ll n,q;
        ll d[N];
        ll l, r, t;
        ll tab[N];
        
     
        int main(){
            //ios::sync_with_stdio(0);
            //freopen("easy.txt","r",stdin);
            cin >> n>> q;
            ll res;
            for(int i=0;i<n;i++)
                scanf("%lld",&d[i]);
            tab[0]=1;
            for(int i=1;i<=n;i++){
                if(tab[i-1]>=d[i]){
                	tab[i]=tab[i-1];
                }else{
                	//cout << d[i]<< endl;
                    tab[i]  = tab[i-1] * ((d[i-1]+tab[i-1]-1)/tab[i-1]);
                }
                
            }
            while(q--){
                ll x, y, t;
                scanf("%lld %lld %lld",&t,&x,&y);
                ll l=0, r=n;
                bool cond=0;
                ll sghir=0;
                ll kbir=0;
                while(l<=r){
                	ll mid=(l+r)/2;
                	ll p = tab[mid]*(t/tab[mid]) -mid;
                	if(p>=x  && p<=y){
                		r=mid-1;
                		sghir=mid;
                		cond=true;
                	}else if(p<x){
                		r=mid-1;
                	}else{
                		l=mid+1;
                	}
                }
                if(cond==0){
                	cout << 0 << endl;
                	continue;
                }
                l=sghir; r=n;
                while(l<=r){
                	ll mid=(l+r)/2;
                	ll p = tab[mid]*(t/tab[mid]) -mid;
                	if(p>=x  && p<=y){
                		l=mid+1;
                		kbir=mid;
                	}else if(p<x){
                		r=mid-1;
                	}else{
                		l=mid+1;
                	}
                	
                }
                printf("%lld\n",kbir-sghir+1);
                
                
             
             
            }
            return 0;
        }

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:29:16: warning: unused variable 'res' [-Wunused-variable]
             ll res;
                ^~~
worst_reporter3.cpp:31:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%lld",&d[i]);
                 ~~~~~^~~~~~~~~~~~~~
worst_reporter3.cpp:44:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%lld %lld %lld",&t,&x,&y);
                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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