Submission #914928

#	Time	Username	Problem	Language	Result	Execution time	Memory
914928		yhkhoo	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	458 ms	29472 KiB

worst_reporter3

#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] = 2000000000;
        }
    }
    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;
            if(hi-lo == 1) m2++;
            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: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 81 / 81