oj.uz

Submission #171814

# Submission time Handle Problem Language Result Execution time Memory
171814 2019-12-30T12:48:23 Z mhy908 Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 1051 ms 25544 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1000000007;
int n, q;
LL d[500010];
LL findx(int num, LL t){
    if(num==0)return t;
    return t/d[num]*d[num]-(LL)num;
}
int f(int st, int fin, LL x, LL t){
    if(st==fin)return st;
    int mid=(st+fin)/2+1;
    LL xx=findx(mid, t);
    if(xx<x)return f(st, mid-1, x, t);
    return f(mid, fin, x, t);
}
int g(int st, int fin, LL x, LL t){
    if(st==fin)return st;
    int mid=(st+fin)/2;
    LL xx=findx(mid, t);
    if(xx>x)return g(mid+1, fin, x, t);
    return g(st, mid, x, t);
}
int main()
{
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++){
        scanf("%lld", &d[i]);
        if(i>1){
            if(d[i]<d[i-1])d[i]=d[i-1];
            d[i]=((d[i]-1)/d[i-1]+1)*d[i-1];
        }
    }
    for(int i=1; i<=q; i++){
        LL a, b, c;
        scanf("%lld %lld %lld", &a, &b, &c);
        int ff=f(0, n, b, a);
        int gg=g(0, n, c, a);
        if(a<b)ff=-1;
        if(findx(n, a)>c)gg=n+1;
        printf("%d\n", ff-gg+1);
    }
}

Compilation message

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:27: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:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &d[i]);
         ~~~~~^~~~~~~~~~~~~~~
worst_reporter3.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 910 ms 7356 KB Output is correct
2 Correct 968 ms 22704 KB Output is correct
3 Correct 907 ms 22776 KB Output is correct
4 Correct 1026 ms 22936 KB Output is correct
5 Correct 1027 ms 22860 KB Output is correct
6 Correct 1051 ms 22772 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 910 ms 7356 KB Output is correct
2 Correct 968 ms 22704 KB Output is correct
3 Correct 907 ms 22776 KB Output is correct
4 Correct 1026 ms 22936 KB Output is correct
5 Correct 1027 ms 22860 KB Output is correct
6 Correct 1051 ms 22772 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 3 ms 416 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 622 ms 21268 KB Output is correct
14 Correct 626 ms 22008 KB Output is correct
15 Correct 606 ms 20472 KB Output is correct
16 Correct 626 ms 21128 KB Output is correct
17 Correct 771 ms 25512 KB Output is correct
18 Correct 768 ms 25544 KB Output is correct
19 Correct 765 ms 25452 KB Output is correct
20 Correct 783 ms 25524 KB Output is correct
21 Correct 771 ms 25352 KB Output is correct
22 Correct 773 ms 25392 KB Output is correct
23 Correct 767 ms 25296 KB Output is correct
24 Correct 777 ms 25328 KB Output is correct
25 Correct 953 ms 22832 KB Output is correct
26 Correct 945 ms 22756 KB Output is correct
27 Correct 826 ms 25048 KB Output is correct
28 Correct 838 ms 25336 KB Output is correct
29 Correct 801 ms 24824 KB Output is correct
30 Correct 866 ms 24988 KB Output is correct
31 Correct 829 ms 25208 KB Output is correct
32 Correct 761 ms 21328 KB Output is correct
33 Correct 2 ms 256 KB Output is correct