oj.uz

Submission #1088976

# Submission time Handle Problem Language Result Execution time Memory
1088976 2024-09-15T17:09:06 Z DobromirAngelov Worst Reporter 3 (JOI18_worst_reporter3) C++14
19 / 100
 341 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)
{
    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];
    }

    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 339 ms 20816 KB Output is correct
2 Correct 341 ms 20816 KB Output is correct
3 Correct 329 ms 20820 KB Output is correct
4 Correct 329 ms 20816 KB Output is correct
5 Correct 321 ms 20820 KB Output is correct
6 Correct 327 ms 20724 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 0 ms 348 KB Output is correct
3 Correct 0 ms 348 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 484 KB Output is correct

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 20816 KB Output is correct
2 Correct 341 ms 20816 KB Output is correct
3 Correct 329 ms 20820 KB Output is correct
4 Correct 329 ms 20816 KB Output is correct
5 Correct 321 ms 20820 KB Output is correct
6 Correct 327 ms 20724 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 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 484 KB Output is correct
13 Runtime error 38 ms 9280 KB Execution killed with signal 8
14 Halted 0 ms 0 KB -