Submission #44417

#	Time	Username	Problem	Language	Result	Execution time	Memory
44417		aome	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	1384 ms	13584 KiB

worst_reporter3

#include <bits/stdc++.h>

using namespace std;

const int N = 500005;

int n, m;
int d[N];
long long a[N];
vector< vector<int> > vec;

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	a[0] = 1;
	for (int i = 1; i <= n; ++i) {
		cin >> d[i];
		int tmp = (d[i] + (a[i - 1] - 1)) / a[i - 1];
		a[i] = tmp * a[i - 1];
	}
	vector<int> cur;
	cur.push_back(0);
	for (int i = 1; i <= n; ++i) {
		if (a[i] != a[cur.back()]) {
			vec.push_back(cur), cur.clear();
		}
		cur.push_back(i);
	}
	vec.push_back(cur);
	for (int i = 1; i <= m; ++i) {
		int t, l, r; cin >> t >> l >> r;
		int res = 0;
		for (int j = 0; j < vec.size(); ++j) {
			int tmp = t / a[vec[j][0]] * a[vec[j][0]];
			int l0 = -vec[j].back(), r0 = -vec[j][0];
			int l1 = l - tmp, r1 = r - tmp;
			l0 = max(l0, l1), r0 = min(r0, r1);
			res += max(0, r0 - l0 + 1);
		}
		cout << res << '\n';
	}
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:33:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < vec.size(); ++j) {
                   ~~^~~~~~~~~~~~

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