Submission #429557

#	Time	Username	Problem	Language	Result	Execution time	Memory
429557		8e7	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	784 ms	29344 KiB

worst_reporter3

//Challenge: Accepted
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <cmath>
#include <assert.h>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
//using namespace __gnu_pbds;
void debug() {cout << endl;}
template <class T, class ...U> void debug(T a, U ... b) { cout << a << " "; debug(b...);}
template <class T> void pary(T l, T r) {
	while (l != r) {cout << *l << " ";l++;}
	cout << endl;
}
#define ll long long
#define ld long double
#define maxn 500005
#define mod 1000000007
#define pii pair<long long, long long>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
ll d[maxn], a[maxn];
int ans(int n, ll t, ll x) {
	int lef = 0, rig = n + 1;
	while (rig > lef + 1) {
		int mid = (lef + rig) / 2;
		ll dis = (-mid) + t - (t % a[mid]);
		if (dis >= x) lef = mid;
		else rig = mid;
	}
	return lef;
}
int main() {
	io
	int n, q;
	cin >> n >> q;
	for (int i = 1;i <= n;i++) cin >> d[i];
	for (int i = 1;i <= n;i++) {
		if (i == 1) a[i] = d[i];
		else a[i] = ((d[i] + a[i - 1] - 1) / a[i - 1]) * a[i - 1]; 
	}
	while (q--) {
		ll t, l, r;
		cin >> t >> l >> r;
		cout << ans(n, t, l) - ans(n, t, r + 1) + (l <= t && t <= r ? 1 : 0) << "\n";
	}	
}

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