oj.uz

Submission #1088985

# Submission time Handle Problem Language Result Execution time Memory
1088985 2024-09-15T17:21:28 Z DobromirAngelov Worst Reporter 3 (JOI18_worst_reporter3) C++14
19 / 100
 349 ms 13320 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

const int MAXN=5e5+5;
const int MAXQ=5e5+5;

int n,q;
int v[MAXN];

int getPos(int ind,int t)
{
    //if(ind<1 || n<ind) ind=1;
    return (t/v[ind])*v[ind]-ind;
}

int bs(int x,int t)
{
    int l=0,r=n;
    while(l<r)
    {
        int mid=(l+r+1)/2;
        if(getPos(mid,t)>=x) l=mid;
        else r=mid-1;
    }
    return l;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>v[i];

    for(int i=2;i<=n;i++)
    {
        v[i]=((v[i]+v[i-1]-1)/v[i-1])*v[i-1];
        if(v[i]==0) v[i]=1;
    }

    for(int i=0;i<q;i++)
    {
        int t,l,r;
        cin>>t>>l>>r;

        int ind1=bs(r+1,t);
        int ind2=bs(l,t);
        int ans=0;
        if(l<=t && t<=r) ans++;
        ans+=ind2-ind1;
        cout<<ans<<endl;
    }

    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 13320 KB Output is correct
2 Correct 327 ms 13136 KB Output is correct
3 Correct 325 ms 13136 KB Output is correct
4 Correct 349 ms 5456 KB Output is correct
5 Correct 317 ms 5204 KB Output is correct
6 Correct 320 ms 5204 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 13320 KB Output is correct
2 Correct 327 ms 13136 KB Output is correct
3 Correct 325 ms 13136 KB Output is correct
4 Correct 349 ms 5456 KB Output is correct
5 Correct 317 ms 5204 KB Output is correct
6 Correct 320 ms 5204 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Incorrect 183 ms 3480 KB Output isn't correct
14 Halted 0 ms 0 KB -