oj.uz

Submission #320030

# Submission time Handle Problem Language Result Execution time Memory
320030 2020-11-07T10:41:25 Z NachoLibre Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 647 ms 25572 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 500005;
int n, q, t, l, r;
long long x[N] = {1};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for(int i = 1; i <= n; ++i) {
		cin >> x[i];
		x[i] = x[i - 1] * ((x[i] - 1) / x[i - 1] + 1);
	}
	for(int qi = 1; qi <= q; ++qi) {
		cin >> t >> l >> r;
		int sl = 0, sr = n;
		if(x[0] * (t / x[0]) < l) sl = sr = -1;
		while(sl < sr) {
			int sm = (sl + sr + 1) / 2;
			if(x[sm] * (t / x[sm]) - sm >= l) {
				sl = sm;
			} else {
				sr = sm - 1;
			}
		}
		int wl = sl;
		sl = 0, sr = n;
		if(x[n] * (t / x[n]) - n > r) sl = sr = n + 1;
		while(sl < sr) {
			int sm = (sl + sr) / 2;
			if(x[sm] * (t / x[sm]) - sm <= r) {
				sr = sm;
			} else {
				sl = sm + 1;
			}
		}
		cout << max(0, wl - sl + 1) << "\n";
	}
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 638 ms 22736 KB Output is correct
2 Correct 635 ms 22888 KB Output is correct
3 Correct 646 ms 22708 KB Output is correct
4 Correct 646 ms 22884 KB Output is correct
5 Correct 647 ms 22732 KB Output is correct
6 Correct 642 ms 22884 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 638 ms 22736 KB Output is correct
2 Correct 635 ms 22888 KB Output is correct
3 Correct 646 ms 22708 KB Output is correct
4 Correct 646 ms 22884 KB Output is correct
5 Correct 647 ms 22732 KB Output is correct
6 Correct 642 ms 22884 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 2 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 375 ms 21432 KB Output is correct
14 Correct 406 ms 21860 KB Output is correct
15 Correct 356 ms 20452 KB Output is correct
16 Correct 367 ms 21092 KB Output is correct
17 Correct 503 ms 25432 KB Output is correct
18 Correct 477 ms 25476 KB Output is correct
19 Correct 471 ms 25520 KB Output is correct
20 Correct 469 ms 25316 KB Output is correct
21 Correct 467 ms 25572 KB Output is correct
22 Correct 457 ms 25316 KB Output is correct
23 Correct 513 ms 25320 KB Output is correct
24 Correct 475 ms 25444 KB Output is correct
25 Correct 647 ms 22828 KB Output is correct
26 Correct 625 ms 22756 KB Output is correct
27 Correct 510 ms 24804 KB Output is correct
28 Correct 511 ms 25196 KB Output is correct
29 Correct 509 ms 25008 KB Output is correct
30 Correct 514 ms 24932 KB Output is correct
31 Correct 529 ms 25060 KB Output is correct
32 Correct 499 ms 21348 KB Output is correct
33 Correct 1 ms 364 KB Output is correct