Submission #358764

#	Time	Username	Problem	Language	Result	Execution time	Memory
358764		ijxjdjd	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	698 ms	27500 KiB

worst_reporter3

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;

using ll = long long;

const int MAXN = (int)(5e5) + 5;
int D[MAXN];
ll moving[MAXN];
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, Q;
	cin >> N >> Q;
    moving[0] = 1;
	for (int i = 1; i <= N; i++) {
        cin >> D[i];
        moving[i] = ((moving[i-1] + D[i]-1)/moving[i-1])*moving[i-1];
	}
	auto getAt = [&] (ll time, int i) {
            return (time/moving[i]) * moving[i] - i;
    };
	FR(i, Q) {
        int t, l, r;
        cin >> t >> l >> r;
        if (getAt(t, 0) < l || getAt(t, N) > r) {
            cout << 0 << '\n';
            continue;
        }
        int low = 0;
        int high = N;
        while (low < high) {
            int mid = (low + high+1)/2;
            if (getAt(t, mid) >= l) {
                low = mid;
            }
            else {
                high = mid-1;
            }
        }
        int slow = low;
        low = 0; high = N;
        while (low < high) {
            int mid = (low + high)/2;
            if (getAt(t, mid) <= r) {
                high = mid;
            }
            else {
                low = mid+1;
            }
        }
        cout << slow-high + 1 << '\n';
	}

	return 0;
}

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