oj.uz

Submission #242206

# Submission time Handle Problem Language Result Execution time Memory
242206 2020-06-27T05:37:35 Z tqbfjotld Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 734 ms 6136 KB 
#include <bits/stdc++.h>
using namespace std;

int n,q;
int arr[500005];

int func(int t, int person){
    if (person==-1) return t;
    if (person==-2) return 1000000005;
    return (t/arr[person])*arr[person]-person-1;
}

int main(){
    scanf("%d%d",&n,&q);
    for (int x = 0; x<n; x++){
        scanf("%d",&arr[x]);
    }
    for (int x = 1; x<n; x++){
        arr[x] = ((arr[x]-1)/arr[x-1])*arr[x-1]+arr[x-1];
    }
    for (int x = 0; x<q; x++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        int lb,rb;
        if (func(a,-1)<b){
            printf("0\n");
            continue;
        }
        if (func(a,n-1)>c){
            printf("0\n");
            continue;
        }
        int l = -1;
        int r = n;
        while (l+1<r){
            int mid = (l+r)/2;
            if (func(a,mid)>=b){
                l = mid;
            }
            else r = mid;
        }
        lb = l;

        l = -2;
        r = n-1;
        while (l+1<r){
            int mid = (l+r)/2;
            //printf("func mid %d\n",func(a,mid));
            if (func(a,mid)<=c){
                r = mid;
            }
            else{
                l = mid;
            }
        }
        rb = r;

        //printf("func(rb): %d\n",func(a,rb));
        printf("%d\n",lb-rb+1);
        //printf("%d %d\n",lb,rb);

    }
}

Compilation message

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 5784 KB Output is correct
2 Correct 728 ms 6136 KB Output is correct
3 Correct 678 ms 6136 KB Output is correct
4 Correct 672 ms 6124 KB Output is correct
5 Correct 670 ms 6136 KB Output is correct
6 Correct 698 ms 6060 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 5784 KB Output is correct
2 Correct 728 ms 6136 KB Output is correct
3 Correct 678 ms 6136 KB Output is correct
4 Correct 672 ms 6124 KB Output is correct
5 Correct 670 ms 6136 KB Output is correct
6 Correct 698 ms 6060 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 459 ms 4040 KB Output is correct
14 Correct 474 ms 3324 KB Output is correct
15 Correct 444 ms 4028 KB Output is correct
16 Correct 508 ms 4160 KB Output is correct
17 Correct 582 ms 4808 KB Output is correct
18 Correct 574 ms 4736 KB Output is correct
19 Correct 567 ms 4740 KB Output is correct
20 Correct 595 ms 4788 KB Output is correct
21 Correct 564 ms 4776 KB Output is correct
22 Correct 559 ms 4840 KB Output is correct
23 Correct 595 ms 4960 KB Output is correct
24 Correct 563 ms 4680 KB Output is correct
25 Correct 734 ms 6076 KB Output is correct
26 Correct 696 ms 5844 KB Output is correct
27 Correct 601 ms 5344 KB Output is correct
28 Correct 613 ms 4972 KB Output is correct
29 Correct 595 ms 5140 KB Output is correct
30 Correct 618 ms 5240 KB Output is correct
31 Correct 603 ms 5068 KB Output is correct
32 Correct 609 ms 5112 KB Output is correct
33 Correct 5 ms 256 KB Output is correct