Submission #997625

#	Time	Username	Problem	Language	Result	Execution time	Memory
997625		vjudge1	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	1151 ms	21588 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
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 >> 1;
        if (a[mid].second + (t - t % a[mid].first) >= x) l = mid;
        else r = mid - 1;
    }
    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() {
    int q, n;
    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});
    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        cout << cnt(l, t) - cnt(r + 1, t) << "\n";
    }
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int cnt(int, int)':
worst_reporter3.cpp:8:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    8 |         int mid = l + r + 1 >> 1;
      |                   ~~~~~~^~~

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