제출 #1251562

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

worst_reporter3

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

ll n, q, l, r, t, arr[500005];
ll per[500005];

ll getpos(int idx, int t) {
    //get position of idx at time t
    return per[idx] * (t / per[idx]) - idx;
}

int gglow(int pos, int t) {
    int l = 0, r = n, mid = -1;
    while(l <= r) {
        mid = (l+r) >> 1;
        if(getpos(mid, t) >= pos) l = mid+1;
        else r = mid - 1;
    }
    return r;
}

int gghi(int pos, int t) {
    int l = 0, r = n, mid = -1;
    while(l <= r) {
        mid = (l+r) >> 1;
        if(getpos(mid, t) > pos) l = mid + 1;
        else r = mid - 1;
    }
    return r;
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> q;
    per[0] = 1;
    for(int i=1;i<=n;i++) {
        cin >> arr[i];
        per[i] = 1ll * per[i-1] * ((arr[i] + per[i-1] - 1) / per[i-1]);
        //cout << per[i] << '\n';
    }
    //period 
    while(q--) {
        cin >> t >> l >> r;
        cout << gglow(l, t) - gghi(r, t) << '\n';
    }
}

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