Submission #429565

#	Time	Username	Problem	Language	Result	Execution time	Memory
429565		Kevin_Zhang_TW	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	456 ms	11280 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// My bug list :
// integer overflow
// 0based, 1based forgotten
// index out of bound
// n, m, i, j typo
// some cases are missing

const int MAX_N = 500010;

int n, q;

// per[i] means how many step last one move, then I move
int D[MAX_N], v[MAX_N], per[MAX_N], len[MAX_N];

void init() {
	v[0] = 1;
	for (int i = 1;i <= n;++i) {
		//per[i] = cdiv(D[i] - 1, v[i-1]);
		per[i] = (D[i]-1) / v[i-1] + 1;
		v[i] = per[i] * v[i-1];
	}
	for (int i = n;i >= 0;--i) {
		len[i] = 1;
		if (per[i+1] == 1) {
			len[i] = len[i+1] + 1;
		}
	}
	per[n+1] = 1;
}

int inter(int l1, int r1, int l2, int r2) {
	chmax(l1, l2);
	chmin(r1, r2);
	return max(0, r1 - l1 + 1);
}
int qry(int t, int l, int r) {
	int res = 0;
	for (int i = 0;i <= n && t > 0;) {
		int at = -i + t * v[i];
		res += inter(at - len[i] + 1, at, l, r);

		i += len[i];
		if (i > n) break;
		t /= per[i];
	}
	return res;
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> q;
	for (int i = 1;i <= n;++i)
		cin >> D[i];

	init();

	while (q--) {
		int t, l, r;
		cin >> t >> l >> r;
		cout << qry(t, l, r) << '\n';
	}
}

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