oj.uz

Submission #535795

# Submission time Handle Problem Language Result Execution time Memory
535795 2022-03-11T09:06:45 Z 79brue Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 754 ms 33300 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, q;
ll arr[500002];
ll ta[500002], len[500002];

int calc(ll t, ll x){
    int l = 0, r = n, ans = -1;
    while(l <= r){
        int m = (l+r)>>1;
        if((t / ta[m]) * len[m] - m >= x){
            ans = m;
            l = m+1;
        }
        else r = m-1;
    }
    return ans;
}

int main(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);

    ta[0] = 1, len[0] = 1;
    for(int i=1; i<=n; i++){
        ta[i] = ta[i-1] * ((arr[i] + len[i-1] - 1) / len[i-1]);
        len[i] = ta[i] / ta[i-1] * len[i-1];
    }

    while(q--){
        ll t, l, r;
        scanf("%lld %lld %lld", &t, &l, &r);
        printf("%d\n", calc(t, l) - calc(t, r+1));
    }
}

Compilation message

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
worst_reporter3.cpp:26:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~
worst_reporter3.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%lld %lld %lld", &t, &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 719 ms 30616 KB Output is correct
2 Correct 710 ms 30540 KB Output is correct
3 Correct 686 ms 30532 KB Output is correct
4 Correct 696 ms 30484 KB Output is correct
5 Correct 672 ms 30556 KB Output is correct
6 Correct 677 ms 30468 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 320 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 320 KB Output is correct
6 Correct 1 ms 320 KB Output is correct

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 719 ms 30616 KB Output is correct
2 Correct 710 ms 30540 KB Output is correct
3 Correct 686 ms 30532 KB Output is correct
4 Correct 696 ms 30484 KB Output is correct
5 Correct 672 ms 30556 KB Output is correct
6 Correct 677 ms 30468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 320 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 320 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 406 ms 28936 KB Output is correct
14 Correct 727 ms 29488 KB Output is correct
15 Correct 407 ms 28168 KB Output is correct
16 Correct 456 ms 28804 KB Output is correct
17 Correct 522 ms 33072 KB Output is correct
18 Correct 501 ms 33120 KB Output is correct
19 Correct 516 ms 33300 KB Output is correct
20 Correct 503 ms 32932 KB Output is correct
21 Correct 492 ms 33032 KB Output is correct
22 Correct 477 ms 33172 KB Output is correct
23 Correct 502 ms 32944 KB Output is correct
24 Correct 504 ms 33104 KB Output is correct
25 Correct 754 ms 30616 KB Output is correct
26 Correct 697 ms 30460 KB Output is correct
27 Correct 550 ms 32640 KB Output is correct
28 Correct 486 ms 32956 KB Output is correct
29 Correct 532 ms 32440 KB Output is correct
30 Correct 540 ms 32552 KB Output is correct
31 Correct 535 ms 32932 KB Output is correct
32 Correct 526 ms 29024 KB Output is correct
33 Correct 0 ms 212 KB Output is correct