Submission #994412

#	Time	Username	Problem	Language	Result	Execution time	Memory
994412		onbert	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	19 / 100	173 ms	18860 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5 + 5, INF = 1e9;
int n;
vector<pair<int,int>> a;
int cnt(int x, int t) {
    int l = 0, r = a.size()-2;
    while (l<r) {
        int mid = (l+r+1)/2;
        if (a[mid].second + (t - t%a[mid].first) >= x) l = mid;
        else r = mid-1;
    }
    // cout << "test " << x << " " << t << " " << l << endl;
    int pos = a[l].second + (t - t%a[l].first);
    if (pos < x) return 0;
    return min(pos - x, a[l].second - a[l+1].second-1) + (-a[l].second + 1);
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int q;
    cin >> n >> q;
    int cur = 0;
    a.push_back({1, 0});
    for (int i=1;i<=n;i++) {
        int x;
        cin >> x;
        if (x > cur && cur <= INF) {
            if (cur==0) cur = x;
            else cur = ((x+cur-1)/cur) * cur;
            if (cur <= INF) a.push_back({cur, -i});
        }
    }
    a.push_back({1e18, -n-1});
    // for (auto [x, y]:a) cout << x << " " << y << endl;
    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        cout << cnt(l, t) - cnt(r+1, t) << "\n";
    }
}

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