Submission #411840

#	Time	Username	Problem	Language	Result	Execution time	Memory
411840		ParsaAlizadeh	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	720 ms	29252 KiB

worst_reporter3

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

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define X first
#define Y second

inline ll ceil(ll x, ll y) {
    return (x + y - 1) / y;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<pair<int, ll>> D(n + 1);
    D[0] = {0, 1};
    for (int i = 1; i <= n; i++) {
        cin >> D[i].Y;
        D[i].X = -i;
        D[i].Y = ceil(D[i].Y, D[i - 1].Y) * D[i - 1].Y;
    }
    while (q --> 0) {
        ll t, l, r;
        cin >> t >> l >> r;
        auto cmp = [&] (const pii& elem, ll r) -> bool {
            int k = t / elem.Y * elem.Y + elem.X;
            return k >= r;
        };
        int ans = lower_bound(begin(D), end(D), l, cmp) - lower_bound(begin(D), end(D), r + 1, cmp);
        cout << ans << '\n';
    }
    return 0;
}

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