Submission #895912

#	Time	Username	Problem	Language	Result	Execution time	Memory
895912		hmm789	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	483 ms	25392 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 998244353

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, q, t, l, r;
    cin >> n >> q;
    int a[n+1];
    a[0] = 1;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = (a[i]+a[i-1]-1)/a[i-1]*a[i-1];
    }
    while(q--) {
        cin >> t >> l >> r;
        int L = 0, R = n+1, m;
        while(L < R) {
            m = (L+R)/2;
            int pos = -m+t/a[m]*a[m];
            if(pos > r) L = m+1;
            else R = m;
        }
        int rpos = L;
        L = 0; R = n+1;
        while(L < R) {
            m = (L+R)/2;
            int pos = -m+t/a[m]*a[m];
            if(pos >= l) L = m+1;
            else R = m;
        }
        int lpos = L;
        cout << lpos-rpos << '\n';
    }
}

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