oj.uz

Submission #817816

# Submission time Handle Problem Language Result Execution time Memory
817816 2023-08-09T17:02:15 Z Alan Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 495 ms 25560 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	vector<int> a {1}, idx {0};
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		a.push_back(x);
		a[i] = max(a[i-1], a[i]);
		a[i] = (a[i]-1) / a[i-1] * a[i-1] + a[i-1];
		idx.push_back(i);
	}
	reverse(idx.begin(), idx.end());
	while (q--) {
		int t, l, r;
		cin >> t >> l >> r;
		auto itl = lower_bound(idx.begin(), idx.end(), l, [&] (int x, int id) {return -x + t / a[x] * a[x] < id;});
		auto itr = upper_bound(idx.begin(), idx.end(), r, [&] (int id, int x) {return id < -x + t / a[x] * a[x];});
		cout << itr - itl << '\n';
	}
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 22884 KB Output is correct
2 Correct 480 ms 22912 KB Output is correct
3 Correct 478 ms 22844 KB Output is correct
4 Correct 483 ms 22868 KB Output is correct
5 Correct 478 ms 23004 KB Output is correct
6 Correct 482 ms 22896 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 22884 KB Output is correct
2 Correct 480 ms 22912 KB Output is correct
3 Correct 478 ms 22844 KB Output is correct
4 Correct 483 ms 22868 KB Output is correct
5 Correct 478 ms 23004 KB Output is correct
6 Correct 482 ms 22896 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 254 ms 21356 KB Output is correct
14 Correct 262 ms 22084 KB Output is correct
15 Correct 240 ms 20640 KB Output is correct
16 Correct 246 ms 21216 KB Output is correct
17 Correct 330 ms 25496 KB Output is correct
18 Correct 335 ms 25428 KB Output is correct
19 Correct 330 ms 25560 KB Output is correct
20 Correct 331 ms 25448 KB Output is correct
21 Correct 334 ms 25512 KB Output is correct
22 Correct 330 ms 25480 KB Output is correct
23 Correct 376 ms 25408 KB Output is correct
24 Correct 328 ms 25500 KB Output is correct
25 Correct 491 ms 22924 KB Output is correct
26 Correct 495 ms 22856 KB Output is correct
27 Correct 372 ms 25020 KB Output is correct
28 Correct 363 ms 25464 KB Output is correct
29 Correct 356 ms 24868 KB Output is correct
30 Correct 394 ms 24996 KB Output is correct
31 Correct 377 ms 25284 KB Output is correct
32 Correct 353 ms 21484 KB Output is correct
33 Correct 0 ms 324 KB Output is correct