oj.uz

Submission #702395

# Submission time Handle Problem Language Result Execution time Memory
702395 2023-02-23T22:27:19 Z urosk Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 486 ms 25340 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000LL
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;

#define maxn 500005
ll n,q;
ll d[maxn];
ll get(ll x,ll t){
    ll l = 0,r = n,mid,rez = 0;
    while(l<=r){
        mid = (l+r)/2;
        if((t/d[mid])*d[mid]-mid>=x) rez = mid+1,l = mid+1;
        else r = mid-1;
    }
    return rez;
}
void tc(){
    cin >> n >> q;
    for(ll i = 1;i<=n;i++) cin >> d[i];
    d[0] = 1;
    for(ll i = 2;i<=n;i++) d[i] = min(iinf,((d[i]+d[i-1]-1)/d[i-1])*d[i-1]);
    while(q--){
        ll l,r,t;
        cin >> t >> l >> r;
        ll L = get(l,t),R = get(r+1,t);
        cout<<L-R<<endl;
    }
}
int main(){
	daj_mi_malo_vremena
    int t; t = 1;
    while(t--){
        tc();
    }
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 7120 KB Output is correct
2 Correct 478 ms 22748 KB Output is correct
3 Correct 486 ms 22716 KB Output is correct
4 Correct 460 ms 22604 KB Output is correct
5 Correct 463 ms 22604 KB Output is correct
6 Correct 482 ms 22712 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 7120 KB Output is correct
2 Correct 478 ms 22748 KB Output is correct
3 Correct 486 ms 22716 KB Output is correct
4 Correct 460 ms 22604 KB Output is correct
5 Correct 463 ms 22604 KB Output is correct
6 Correct 482 ms 22712 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 298 ms 21272 KB Output is correct
14 Correct 295 ms 21772 KB Output is correct
15 Correct 281 ms 20588 KB Output is correct
16 Correct 287 ms 20920 KB Output is correct
17 Correct 372 ms 25244 KB Output is correct
18 Correct 400 ms 25248 KB Output is correct
19 Correct 361 ms 25284 KB Output is correct
20 Correct 388 ms 25228 KB Output is correct
21 Correct 358 ms 25264 KB Output is correct
22 Correct 356 ms 25340 KB Output is correct
23 Correct 358 ms 25212 KB Output is correct
24 Correct 349 ms 25280 KB Output is correct
25 Correct 482 ms 22796 KB Output is correct
26 Correct 480 ms 22768 KB Output is correct
27 Correct 396 ms 24748 KB Output is correct
28 Correct 384 ms 25120 KB Output is correct
29 Correct 396 ms 24652 KB Output is correct
30 Correct 389 ms 24744 KB Output is correct
31 Correct 401 ms 25160 KB Output is correct
32 Correct 375 ms 21276 KB Output is correct
33 Correct 0 ms 212 KB Output is correct