Submission #67163

#	Time	Username	Problem	Language	Result	Execution time	Memory
67163		imeimi2000	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	1285 ms	191524 KiB

worst_reporter3

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n;
llong d[500001];

int getPos(int i, int t) {
    return i - t / d[i] * d[i];
}

int lowbound(int x, int t) {
    int s = 0, e = n + 1;
    while (s < e) {
        int m = (s + e) / 2;
        if (getPos(m, t) < x) s = m + 1;
        else e = m;
    }
    return s;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int q;
	cin >> n >> q;
	d[0] = 1;
	for (int i = 1; i <= n; ++i) {
        cin >> d[i];
        d[i] = ((d[i] - 1) / d[i - 1] + 1) * d[i - 1];
	}
	
	while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        printf("%d\n", lowbound(-l + 1, t) - lowbound(-r, t));
	}
	return 0;
}

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