oj.uz

Submission #917147

# Submission time Handle Problem Language Result Execution time Memory
917147 2024-01-27T10:04:36 Z alexdd Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 490 ms 33272 KB 
#include<bits/stdc++.h>
using namespace std;
/*ifstream fin("input.in");
ofstream fout("output.out");
#define cin fin
#define cout fout*/
#define int long long
int n,q;
int d[500005];
int p[500005];
int ultmare[500005];
int calc_cur(int j, int t)
{
    int i = ultmare[j];
    return (-i + (t/p[i]) * p[i]) - (j - i);
}
void calc_p()
{
    int mxm=d[1];
    p[1]=d[1];
    ultmare[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(d[i]>=mxm)
        {
            mxm=((d[i]-1)/mxm + 1)*mxm;
            p[i]=mxm;
            ultmare[i]=i;
        }
        else
        {
            ultmare[i]=ultmare[i-1];
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>d[i];
    calc_p();
    int le,ri,t;
    while(q--)
    {
        cin>>t>>le>>ri;
        int cnt=0;
        if(le<=t && t<=ri)
            cnt++;
        if(calc_cur(n,t)<=ri && calc_cur(1,t)>=le)
        {
            int st,dr,mij,ans=1;
            st=1;
            dr=n;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(calc_cur(mij,t)<=ri)
                {
                    ans=mij;
                    dr=mij-1;
                }
                else
                    st=mij+1;
            }
            cnt -= ans;

            ans=n;
            st=1;
            dr=n;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(calc_cur(mij,t)>=le)
                {
                    ans=mij;
                    st=mij+1;
                }
                else
                    dr=mij-1;
            }
            cnt += ans + 1;
        }
        cout<<cnt<<"\n";
    }
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 29456 KB Output is correct
2 Correct 469 ms 30548 KB Output is correct
3 Correct 490 ms 30544 KB Output is correct
4 Correct 473 ms 30548 KB Output is correct
5 Correct 473 ms 30656 KB Output is correct
6 Correct 467 ms 30656 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 29456 KB Output is correct
2 Correct 469 ms 30548 KB Output is correct
3 Correct 490 ms 30544 KB Output is correct
4 Correct 473 ms 30548 KB Output is correct
5 Correct 473 ms 30656 KB Output is correct
6 Correct 467 ms 30656 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 2 ms 4440 KB Output is correct
11 Correct 2 ms 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 216 ms 27124 KB Output is correct
14 Correct 241 ms 27856 KB Output is correct
15 Correct 166 ms 26132 KB Output is correct
16 Correct 235 ms 26848 KB Output is correct
17 Correct 325 ms 33104 KB Output is correct
18 Correct 327 ms 33244 KB Output is correct
19 Correct 321 ms 33272 KB Output is correct
20 Correct 327 ms 33168 KB Output is correct
21 Correct 326 ms 33108 KB Output is correct
22 Correct 324 ms 33116 KB Output is correct
23 Correct 323 ms 33004 KB Output is correct
24 Correct 321 ms 33108 KB Output is correct
25 Correct 468 ms 30528 KB Output is correct
26 Correct 478 ms 30612 KB Output is correct
27 Correct 355 ms 32568 KB Output is correct
28 Correct 354 ms 33156 KB Output is correct
29 Correct 365 ms 32592 KB Output is correct
30 Correct 353 ms 32572 KB Output is correct
31 Correct 361 ms 33188 KB Output is correct
32 Correct 354 ms 29216 KB Output is correct
33 Correct 1 ms 4444 KB Output is correct