oj.uz

Submission #775069

# Submission time Handle Problem Language Result Execution time Memory
775069 2023-07-06T07:18:38 Z adaawf Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 1370 ms 26568 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() {
    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 1269 ms 26484 KB Output is correct
2 Correct 1263 ms 26524 KB Output is correct
3 Correct 1354 ms 26472 KB Output is correct
4 Correct 1262 ms 26568 KB Output is correct
5 Correct 1269 ms 26496 KB Output is correct
6 Correct 1261 ms 26564 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1269 ms 26484 KB Output is correct
2 Correct 1263 ms 26524 KB Output is correct
3 Correct 1354 ms 26472 KB Output is correct
4 Correct 1262 ms 26568 KB Output is correct
5 Correct 1269 ms 26496 KB Output is correct
6 Correct 1261 ms 26564 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 316 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1083 ms 25040 KB Output is correct
14 Correct 1110 ms 22844 KB Output is correct
15 Correct 1048 ms 24252 KB Output is correct
16 Correct 1068 ms 24964 KB Output is correct
17 Correct 1194 ms 23572 KB Output is correct
18 Correct 1254 ms 23524 KB Output is correct
19 Correct 1265 ms 20288 KB Output is correct
20 Correct 1211 ms 23736 KB Output is correct
21 Correct 1202 ms 23636 KB Output is correct
22 Correct 1248 ms 22012 KB Output is correct
23 Correct 1210 ms 23528 KB Output is correct
24 Correct 1236 ms 22100 KB Output is correct
25 Correct 1284 ms 26532 KB Output is correct
26 Correct 1318 ms 26468 KB Output is correct
27 Correct 1370 ms 11376 KB Output is correct
28 Correct 1275 ms 23780 KB Output is correct
29 Correct 1331 ms 11328 KB Output is correct
30 Correct 1329 ms 11352 KB Output is correct
31 Correct 1307 ms 11332 KB Output is correct
32 Correct 1239 ms 25128 KB Output is correct
33 Correct 0 ms 212 KB Output is correct