oj.uz

Submission #124654

# Submission time Handle Problem Language Result Execution time Memory
124654 2019-07-03T16:37:34 Z Mtaylor Worst Reporter 3 (JOI18_worst_reporter3) C++17
12 / 100
 2000 ms 10356 KB 
    #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;
                cin >> 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;
                	}
                	
                }
                cout << kbir-sghir+1 << endl;
                
                
             
             
            }
            return 0;
        }

Compilation message

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]);
                 ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2019 ms 10356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 6 ms 380 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 6 ms 344 KB Output is correct

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2019 ms 10356 KB Time limit exceeded
2 Halted 0 ms 0 KB -