oj.uz

Submission #1088984

# Submission time Handle Problem Language Result Execution time Memory
1088984 2024-09-15T17:21:07 Z DobromirAngelov Worst Reporter 3 (JOI18_worst_reporter3) C++14
19 / 100
 345 ms 20820 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 345 ms 20816 KB Output is correct
2 Correct 326 ms 20688 KB Output is correct
3 Correct 332 ms 20636 KB Output is correct
4 Correct 339 ms 20504 KB Output is correct
5 Correct 323 ms 20672 KB Output is correct
6 Correct 327 ms 20820 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 476 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 1 ms 476 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 345 ms 20816 KB Output is correct
2 Correct 326 ms 20688 KB Output is correct
3 Correct 332 ms 20636 KB Output is correct
4 Correct 339 ms 20504 KB Output is correct
5 Correct 323 ms 20672 KB Output is correct
6 Correct 327 ms 20820 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 476 KB Output is correct
9 Correct 1 ms 436 KB Output is correct
10 Correct 1 ms 476 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Incorrect 206 ms 19520 KB Output isn't correct
14 Halted 0 ms 0 KB -