oj.uz

Submission #914925

# Submission time Handle Problem Language Result Execution time Memory
914925 2024-01-23T00:25:12 Z yhkhoo Worst Reporter 3 (JOI18_worst_reporter3) C++17
0 / 100
 2000 ms 9308 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
    cin.tie(0); ios_base::sync_with_stdio(0);
    int n, q;
    cin >> n >> q;
    int d[n];
    for(int i=0; i<n; i++){
        cin >> d[i];
    }
    int cyc[n+1];
    int running=1;
    for(int i=0; i<=n; i++){
        if(running <= 1000000000){
            cyc[i] = running;
            running *= d[i]/running + (d[i]%running != 0);
        }
        else{
            cyc[i] = 0;
        }
    }
    while(q--){
        int t, l, r;
        cin >> t >> l >> r;
        int lo=0, hi=n, m1;
        while(lo<hi){
            m1 = (lo+hi)/2;
            if(hi-lo == 1) m1++;
            int ccyc = cyc[m1];
            int tra = (t/ccyc) * ccyc;
            tra -= m1;
            if(tra < l){
                hi = m1-1;
            }
            else if(tra > l){
                lo = m1;
            }
            else{
                lo = m1;
                hi = m1;
            }
        }
        m1 = lo;
        if(m1 == 0 && t<l){
            m1--;
        }
        lo = 0;
        hi = n;
        int m2 = lo;
        while(lo<hi){
            m2 = (lo+hi)/2;
            int ccyc = cyc[m2];
            int tra = (t/ccyc) * ccyc;
            tra -= m2;
            if(tra <= r){
                hi = m2-1;
            }
            else{
                lo = m2;
            }
        }
        m2 = lo;
        if(m2 == 0 && t<=r){
            m2--;
        }
        cout << m1-m2 << '\n';
    }
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2032 ms 9308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2005 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2032 ms 9308 KB Time limit exceeded
2 Halted 0 ms 0 KB -