oj.uz

Submission #205532

# Submission time Handle Problem Language Result Execution time Memory
205532 2020-02-29T06:07:45 Z PeppaPig Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 935 ms 29396 KB 
#include <bits/stdc++.h>

#define long long long

using namespace std;

const int N = 5e5+5;

int n, q;
long s[N], t[N];

int cnt(long T, long R) {
    int l = 0, r = n;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(s[mid] * (T / t[mid]) - mid <= R) r = mid;
        else l = mid + 1;
    }
    if(s[r] * (T / t[r]) - r <= R) return n + 1 - r;
    else return 0;
}

int main() {
    scanf("%d %d", &n, &q);
    s[0] = t[0] = 1;
    for(int i = 1, d; i <= n; i++) {
        scanf("%d", &d);
        long k = d / s[i-1] + (d % s[i-1] != 0);
        s[i] = s[i-1] * k, t[i] = t[i-1] * k;
    }
    for(int i = 1, t, l, r; i <= q; i++) {
        scanf("%d %d %d", &t, &l, &r);
        printf("%d\n", cnt(t, r) - cnt(t, l-1));
    }

    return 0;
}

Compilation message

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~~
worst_reporter3.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &d);
         ~~~~~^~~~~~~~~~
worst_reporter3.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &t, &l, &r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 902 ms 11384 KB Output is correct
2 Correct 904 ms 26580 KB Output is correct
3 Correct 913 ms 26744 KB Output is correct
4 Correct 917 ms 26684 KB Output is correct
5 Correct 931 ms 26740 KB Output is correct
6 Correct 913 ms 26916 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 902 ms 11384 KB Output is correct
2 Correct 904 ms 26580 KB Output is correct
3 Correct 913 ms 26744 KB Output is correct
4 Correct 917 ms 26684 KB Output is correct
5 Correct 931 ms 26740 KB Output is correct
6 Correct 913 ms 26916 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 499 ms 25056 KB Output is correct
14 Correct 511 ms 26008 KB Output is correct
15 Correct 497 ms 24340 KB Output is correct
16 Correct 496 ms 24952 KB Output is correct
17 Correct 630 ms 29176 KB Output is correct
18 Correct 628 ms 29396 KB Output is correct
19 Correct 619 ms 29176 KB Output is correct
20 Correct 630 ms 29304 KB Output is correct
21 Correct 641 ms 29228 KB Output is correct
22 Correct 630 ms 29304 KB Output is correct
23 Correct 636 ms 29364 KB Output is correct
24 Correct 628 ms 29276 KB Output is correct
25 Correct 902 ms 26592 KB Output is correct
26 Correct 935 ms 26680 KB Output is correct
27 Correct 705 ms 28824 KB Output is correct
28 Correct 675 ms 29108 KB Output is correct
29 Correct 667 ms 28792 KB Output is correct
30 Correct 717 ms 28664 KB Output is correct
31 Correct 670 ms 29048 KB Output is correct
32 Correct 644 ms 25304 KB Output is correct
33 Correct 5 ms 376 KB Output is correct