제출 #1162641

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162641		Hamed_Ghaffari	Worst Reporter 3 (JOI18_worst_reporter3)	C++20	100 / 100	391 ms	11180 KiB

worst_reporter3

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

const int MXN = 5e5+5;

int n, q;
ll a[MXN], b[MXN];

int get(ll t, ll x) {
    int l=-1, r=n+1;
    ll mid;
    while(r-l>1) {
        mid = (l+r)>>1;
        (-mid + (t/a[mid])*b[mid] >= x ? l : r) = mid;
    }
    return l+1;
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> q;
    a[0] = b[0] = 1;
    for(int i=1; i<=n; i++) {
        ll d;
        cin >> d;
        ll x = (d+b[i-1]-1)/b[i-1];
        a[i] = a[i-1]*x;
        b[i] = b[i-1]*x;
    }
    while(q--) {
        int t, l, r;
        cin >> t >> l >> r;
        cout << get(t, l) - get(t, r+1) << '\n';
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 81 / 81