oj.uz

Submission #389093

# Submission time Handle Problem Language Result Execution time Memory
389093 2021-04-13T15:44:18 Z denkendoemeer Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 765 ms 29316 KB 
#include<bits/stdc++.h>
#define ll long long
const int inf=1e9;
using namespace std;
ll d[600006],dp[600005];
int n;
int calc(ll x,ll t)
{
    ll st=-1,dr=n+1;
    while(dr-st>1){
        int mij=(st+dr)/2;
        if (-mij+(t/dp[mij])*dp[mij]>=x)
            st=mij;
        else
            dr=mij;
    }
    return dr;
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int q,i;
    scanf("%d%d",&n,&q);
    for(i=1;i<=n;i++)
        scanf("%lld",&d[i]);
    dp[0]=1;
    for(i=1;i<=n;i++){
        ll aux=(d[i]+dp[i-1]-1)/dp[i-1];
        dp[i]=aux*dp[i-1];
    }
    for(i=1;i<=q;i++){
        ll t,l,r;
        scanf("%lld%lld%lld",&t,&l,&r);
        printf("%d\n",calc(l,t)-calc(r+1,t));
    }
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]
   24 |     scanf("%d%d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~
worst_reporter3.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |         scanf("%lld",&d[i]);
      |         ~~~~~^~~~~~~~~~~~~~
worst_reporter3.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |         scanf("%lld%lld%lld",&t,&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 26552 KB Output is correct
2 Correct 765 ms 26556 KB Output is correct
3 Correct 724 ms 26528 KB Output is correct
4 Correct 728 ms 26512 KB Output is correct
5 Correct 721 ms 26556 KB Output is correct
6 Correct 735 ms 26564 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 26552 KB Output is correct
2 Correct 765 ms 26556 KB Output is correct
3 Correct 724 ms 26528 KB Output is correct
4 Correct 728 ms 26512 KB Output is correct
5 Correct 721 ms 26556 KB Output is correct
6 Correct 735 ms 26564 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 502 ms 25044 KB Output is correct
14 Correct 519 ms 25696 KB Output is correct
15 Correct 499 ms 24272 KB Output is correct
16 Correct 490 ms 24936 KB Output is correct
17 Correct 570 ms 29316 KB Output is correct
18 Correct 585 ms 29100 KB Output is correct
19 Correct 564 ms 29124 KB Output is correct
20 Correct 569 ms 29244 KB Output is correct
21 Correct 581 ms 29152 KB Output is correct
22 Correct 581 ms 29224 KB Output is correct
23 Correct 586 ms 29156 KB Output is correct
24 Correct 564 ms 29252 KB Output is correct
25 Correct 740 ms 26728 KB Output is correct
26 Correct 729 ms 26640 KB Output is correct
27 Correct 633 ms 28644 KB Output is correct
28 Correct 600 ms 29024 KB Output is correct
29 Correct 603 ms 28600 KB Output is correct
30 Correct 621 ms 28844 KB Output is correct
31 Correct 603 ms 28984 KB Output is correct
32 Correct 582 ms 25156 KB Output is correct
33 Correct 1 ms 204 KB Output is correct