oj.uz

Submission #124681

# Submission time Handle Problem Language Result Execution time Memory
124681 2019-07-03T17:15:41 Z Mtaylor Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 1273 ms 29364 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;
            for(int i=0;i<n;i++)
                scanf("%lld",&d[i]);
            tab[0]=1;
            for(int i=1;i<n+1;i++){
                if(tab[i-1]>=d[i-1]){
                	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

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:30: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:43: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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1273 ms 11644 KB Output is correct
2 Correct 1217 ms 13700 KB Output is correct
3 Correct 1170 ms 13724 KB Output is correct
4 Correct 1197 ms 13948 KB Output is correct
5 Correct 1173 ms 13704 KB Output is correct
6 Correct 1183 ms 13816 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1273 ms 11644 KB Output is correct
2 Correct 1217 ms 13700 KB Output is correct
3 Correct 1170 ms 13724 KB Output is correct
4 Correct 1197 ms 13948 KB Output is correct
5 Correct 1173 ms 13704 KB Output is correct
6 Correct 1183 ms 13816 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 4 ms 376 KB Output is correct
10 Correct 4 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 1089 ms 11452 KB Output is correct
14 Correct 984 ms 25668 KB Output is correct
15 Correct 1182 ms 24380 KB Output is correct
16 Correct 1096 ms 24996 KB Output is correct
17 Correct 985 ms 29176 KB Output is correct
18 Correct 977 ms 29304 KB Output is correct
19 Correct 956 ms 29364 KB Output is correct
20 Correct 973 ms 29280 KB Output is correct
21 Correct 1014 ms 29156 KB Output is correct
22 Correct 970 ms 29196 KB Output is correct
23 Correct 982 ms 29144 KB Output is correct
24 Correct 956 ms 29252 KB Output is correct
25 Correct 1202 ms 26772 KB Output is correct
26 Correct 1224 ms 26640 KB Output is correct
27 Correct 1029 ms 28756 KB Output is correct
28 Correct 1027 ms 29032 KB Output is correct
29 Correct 1006 ms 28616 KB Output is correct
30 Correct 1091 ms 28732 KB Output is correct
31 Correct 1028 ms 28940 KB Output is correct
32 Correct 1248 ms 25244 KB Output is correct
33 Correct 2 ms 376 KB Output is correct