oj.uz

Submission #172129

# Submission time Handle Problem Language Result Execution time Memory
172129 2019-12-31T09:40:59 Z balbit Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 862 ms 29492 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define FOR(i,a,b) for (int i=(a); i<(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for (int i=(n-1); i>=0; --i)
#define REP1(i,n) FOR(i,1,n+1)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1<<29;
const ll inf = 1ll<<60;
const ll mod = 1e9+7;


void GG(){cout<<"-1\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b) % mo;
}

const int maxn = 5e5+5;

ll d[maxn], tme[maxn], dst[maxn]; // tme: time for each move, dst: dist of each move
int n;

int nleq(ll T, int x) {
    int l = 0, r = n+1;
//    bug(T);
    while (l!=r) {
        int m = (l+r)/2;
        int at = int(T/dst[m]) * dst[m] -m;
//        bug(m,at);
        if (at <= x) {
            r=m;
        }else{
            l=m+1;
        }
    }
    return n-l;
}

signed main(){
    IOS();
    int q; cin>>n>>q;
    d[0]=tme[0]=dst[0] = 1; // IOI-chan
    REP1(i,n) {
        cin>>d[i];
        dst[i] = int((d[i]+dst[i-1]-1)/dst[i-1]) * dst[i-1];
        bug(i,d[i],dst[i]);
    }
    while (q--) {
        ll t,l,r;
        cin>>t>>l>>r;
        cout<<nleq(t,r)-nleq(t,l-1)<<endl;
    }

}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 862 ms 26744 KB Output is correct
2 Correct 854 ms 26756 KB Output is correct
3 Correct 825 ms 26616 KB Output is correct
4 Correct 836 ms 26704 KB Output is correct
5 Correct 840 ms 26744 KB Output is correct
6 Correct 840 ms 26788 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 432 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 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 862 ms 26744 KB Output is correct
2 Correct 854 ms 26756 KB Output is correct
3 Correct 825 ms 26616 KB Output is correct
4 Correct 836 ms 26704 KB Output is correct
5 Correct 840 ms 26744 KB Output is correct
6 Correct 840 ms 26788 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 432 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 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 565 ms 24912 KB Output is correct
14 Correct 571 ms 25884 KB Output is correct
15 Correct 558 ms 24568 KB Output is correct
16 Correct 564 ms 24856 KB Output is correct
17 Correct 699 ms 29304 KB Output is correct
18 Correct 706 ms 28940 KB Output is correct
19 Correct 702 ms 29492 KB Output is correct
20 Correct 704 ms 29396 KB Output is correct
21 Correct 708 ms 28972 KB Output is correct
22 Correct 714 ms 29304 KB Output is correct
23 Correct 704 ms 28880 KB Output is correct
24 Correct 708 ms 29180 KB Output is correct
25 Correct 851 ms 26360 KB Output is correct
26 Correct 852 ms 26744 KB Output is correct
27 Correct 742 ms 28512 KB Output is correct
28 Correct 718 ms 29048 KB Output is correct
29 Correct 755 ms 28532 KB Output is correct
30 Correct 780 ms 29048 KB Output is correct
31 Correct 757 ms 28696 KB Output is correct
32 Correct 674 ms 25500 KB Output is correct
33 Correct 2 ms 376 KB Output is correct