oj.uz

Submission #242545

# Submission time Handle Problem Language Result Execution time Memory
242545 2020-06-28T07:26:45 Z lyc Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 933 ms 29304 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ll=long long;

const int mxN = 5e5+5;
const int mxQ = 5e5+5;
const int mxT = 2e9;

int N, Q, D[mxN];
int W[mxN], Len[mxN], pW[mxN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> Q;
    FOR(i,1,N){
        cin >> D[i];
    }
    Len[0] = 1;
    W[0] = 1;
    pW[0] = 1;
    FOR(i,1,N){
        W[i] = (D[i]-1)/Len[i-1] + 1;
        { ll tmp = (ll) pW[i-1] * W[i];
        if (tmp > mxT) pW[i] = -1;
        else pW[i] = tmp; }
        { ll tmp = (ll) W[i] * Len[i-1];
        if (tmp > mxT) Len[i] = -1;
        else Len[i] = tmp; }
        //TRACE(W[i] _ Len[i] _ pW[i]);
    }

    FOR(i,1,Q){
        int T, L, R; cin >> T >> L >> R;

        int fst, lst;
        { int lo = -1, hi = N+1;
        while (hi-lo > 1) {
            int mid = (lo+hi)/2;
            if (pW[mid] == -1 || (ll)T/pW[mid]*Len[mid] - mid <= R) hi = mid;
            else lo = mid;
        } 
        fst = hi; }
        { int lo = -1, hi = N+1;
        while (hi-lo > 1) {
            int mid = (lo+hi)/2;
            if (pW[mid] == -1 || (ll)T/pW[mid]*Len[mid] - mid < L) hi = mid;
            else lo = mid;
        } 
        lst = hi; }
        cout << lst-fst << '\n';
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 26744 KB Output is correct
2 Correct 710 ms 26872 KB Output is correct
3 Correct 902 ms 26744 KB Output is correct
4 Correct 759 ms 26680 KB Output is correct
5 Correct 752 ms 26872 KB Output is correct
6 Correct 828 ms 26872 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 26744 KB Output is correct
2 Correct 710 ms 26872 KB Output is correct
3 Correct 902 ms 26744 KB Output is correct
4 Correct 759 ms 26680 KB Output is correct
5 Correct 752 ms 26872 KB Output is correct
6 Correct 828 ms 26872 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 510 ms 25296 KB Output is correct
14 Correct 512 ms 25696 KB Output is correct
15 Correct 500 ms 24512 KB Output is correct
16 Correct 513 ms 25080 KB Output is correct
17 Correct 611 ms 29304 KB Output is correct
18 Correct 657 ms 29176 KB Output is correct
19 Correct 578 ms 29176 KB Output is correct
20 Correct 574 ms 29304 KB Output is correct
21 Correct 639 ms 29304 KB Output is correct
22 Correct 642 ms 29268 KB Output is correct
23 Correct 595 ms 29176 KB Output is correct
24 Correct 594 ms 29304 KB Output is correct
25 Correct 900 ms 26664 KB Output is correct
26 Correct 933 ms 26744 KB Output is correct
27 Correct 622 ms 28920 KB Output is correct
28 Correct 633 ms 29052 KB Output is correct
29 Correct 666 ms 28664 KB Output is correct
30 Correct 674 ms 28896 KB Output is correct
31 Correct 614 ms 29048 KB Output is correct
32 Correct 586 ms 25208 KB Output is correct
33 Correct 5 ms 384 KB Output is correct