Submission #1166205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166205		nuutsnoynton	Worst Reporter 3 (JOI18_worst_reporter3)	C++20	100 / 100	840 ms	11080 KiB

worst_reporter3

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
	ll n, m, r, x, y, lef, rig,cnt, p, i, j, ans, t, ti, lo, hi, q;
	
	cin >> n >> q;
	
	ll a[ n + 2], b[n + 2], c[n + 2];
	
	for (i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	b[0] = 1;
	vector < ll > v;
	
	v.push_back(0);
	for (i = 1; i <= n; i ++) {
		if ( a[i] <= b[i - 1]) {
			b[i] = b[i -1];
		}
		else {
			v.push_back(i);
			b[i] = (a[i] + b[i - 1] - 1)/b[i- 1];
			b[i] = b[i - 1] * b[i];
		}
	}
	v.push_back(n + 1);
	while ( q --) {
		cin >> ti >> lo >> hi;
		cnt = 0;
		for (i = 0; i + 1 < v.size(); i ++) {
			p = ti/b[v[i]];
			p = p * b[v[i]];
			p = p - v[i];
			rig = p;
			lef = p - (v[i + 1] - v[i])+1 ;
		//	cout << lef << " "<< rig << endl;
			if ( lef > hi || lo > rig) continue;
			lef = max(lef, lo);
			rig = min(rig, hi);
			cnt += (rig - lef + 1);
		}
		cout << cnt << "\n";
	}
	
	
	
}

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