Submission #1203381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203381		quannnguyen2009	Worst Reporter 3 (JOI18_worst_reporter3)	C++20	100 / 100	313 ms	11164 KiB

worst_reporter3

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 5e5+5, mod = 1e9+7, inf = 1e18;

int n, q;
int a[N];
int c[N];

int cal(int x, int t) {
    int lo = 1, hi = n, ans = 0;
    while(lo<=hi) {
        int mid = (lo+hi)>>1;
        if (t/c[mid]*c[mid]-mid>=x) {
            ans = mid;
            lo = mid+1;
        } else {
            hi = mid-1;
        }
    }
    return ans;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i=1; i<=n; i++) cin >> a[i];
    c[1] = a[1];
    for (int i=2; i<=n; i++) c[i] = ceil(a[i]*1.0/c[i-1])*c[i-1];
    while(q--) {
        int t, l, r; cin >> t >> l >> r;
        cout << cal(l, t)-cal(r+1, t)+(t>=l && t<=r) << '\n';
    }
}

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