oj.uz

Submission #775071

# Submission time Handle Problem Language Result Execution time Memory
775071 2023-07-06T07:19:48 Z vjudge1 Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 428 ms 11140 KB 
#include <iostream>
using namespace std;
long long int n, a[500005], f[500005];
long long int check(long long int x, long long int i) {
    return x / f[i] * f[i] - i;
}
int trya(long long int t, long long int x) {
    int l = 0, r = n, res = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(t, mid) >= x) {
            res = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return res + 1;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int q;
    cin >> n >> q;
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        f[i] = (a[i] + f[i - 1] - 1) / f[i - 1] * f[i - 1];
    }
    for (int jj = 0; jj < q; jj++) {
        long long int t, l, r;
        cin >> t >> l >> r;
        if (t < l) {
            cout << 0 << '\n';
            continue;
        }
        if (t == l) {
            cout << 1 << '\n';
            continue;
        }
        long long int h = trya(t, l), k = trya(t, r + 1);
        cout << h - k << '\n';
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 11140 KB Output is correct
2 Correct 412 ms 11084 KB Output is correct
3 Correct 412 ms 11060 KB Output is correct
4 Correct 428 ms 11092 KB Output is correct
5 Correct 416 ms 11084 KB Output is correct
6 Correct 421 ms 11032 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 419 ms 11140 KB Output is correct
2 Correct 412 ms 11084 KB Output is correct
3 Correct 412 ms 11060 KB Output is correct
4 Correct 428 ms 11092 KB Output is correct
5 Correct 416 ms 11084 KB Output is correct
6 Correct 421 ms 11032 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 244 ms 9096 KB Output is correct
14 Correct 243 ms 9108 KB Output is correct
15 Correct 233 ms 9092 KB Output is correct
16 Correct 234 ms 9100 KB Output is correct
17 Correct 302 ms 10544 KB Output is correct
18 Correct 309 ms 10480 KB Output is correct
19 Correct 306 ms 10480 KB Output is correct
20 Correct 306 ms 10616 KB Output is correct
21 Correct 311 ms 10548 KB Output is correct
22 Correct 311 ms 10464 KB Output is correct
23 Correct 304 ms 10564 KB Output is correct
24 Correct 318 ms 10604 KB Output is correct
25 Correct 412 ms 11092 KB Output is correct
26 Correct 411 ms 11032 KB Output is correct
27 Correct 349 ms 10964 KB Output is correct
28 Correct 323 ms 10820 KB Output is correct
29 Correct 332 ms 10860 KB Output is correct
30 Correct 335 ms 10984 KB Output is correct
31 Correct 362 ms 10836 KB Output is correct
32 Correct 331 ms 10580 KB Output is correct
33 Correct 0 ms 212 KB Output is correct