제출 #1256099

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

worst_reporter3

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

#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>

const int N = 5e5 + 5;

int n, q;
ll a[N];

int cal(int i, int t) {
    if (t <= i) return n + 1;
    int l = 1, r = n;
    int ans = n + 1;
    while(l <= r) {
        int mid = (l + r) / 2;
        int pos = t - (t % a[mid]) - mid;
        if (pos <= i) {
            r = mid - 1;
            ans = mid;
        }
        else {
            l = mid + 1;
        }
    }
    return n - ans + 1;
}

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

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