oj.uz

Submission #723337

# Submission time Handle Problem Language Result Execution time Memory
723337 2023-04-13T15:48:28 Z mariowong Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 1376 ms 33124 KB 
#include <bits/stdc++.h>
using namespace std;

long long d[500005],p[500005],s[500005];
int main(){
	ios::sync_with_stdio(false);
	int n,q;
	cin >> n >> q;
	for (int i=1;i<=n;i++) cin >> d[i];
	p[0]=s[0]=d[0]=1;
	for (int i=1;i<=n;i++) p[i]=((d[i]-1)/s[i-1]+1)*p[i-1],s[i]=((d[i]-1)/s[i-1]+1)*s[i-1];
	for (int i=1;i<=q;i++){
		long long T,l,r;
		cin >> T >> l >> r;
		int bl=0,br=n;
		while (bl < br){
			int bmid=(bl+br+1)/2;
			if (T/p[bmid]*s[bmid]-bmid < l) br=bmid-1;
			else bl=bmid;
		}
		if (T/p[bl]*s[bl]-bl < l) bl--;
		int ansr=bl;
		bl=0,br=n;
		while (bl < br){
			int bmid=(bl+br)/2;
			if (T/p[bmid]*s[bmid]-bmid > r) bl=bmid+1;
			else br=bmid;
		}
		if (T/p[bl]*s[bl]-bl > r) bl++;
		int ansl=bl;
		cout << ansr-ansl+1 << "\n";	
	}
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1213 ms 30628 KB Output is correct
2 Correct 1209 ms 30652 KB Output is correct
3 Correct 1232 ms 30524 KB Output is correct
4 Correct 1197 ms 30544 KB Output is correct
5 Correct 1196 ms 30440 KB Output is correct
6 Correct 1184 ms 30508 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1213 ms 30628 KB Output is correct
2 Correct 1209 ms 30652 KB Output is correct
3 Correct 1232 ms 30524 KB Output is correct
4 Correct 1197 ms 30544 KB Output is correct
5 Correct 1196 ms 30440 KB Output is correct
6 Correct 1184 ms 30508 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 906 ms 29040 KB Output is correct
14 Correct 891 ms 29588 KB Output is correct
15 Correct 984 ms 28252 KB Output is correct
16 Correct 989 ms 28772 KB Output is correct
17 Correct 1229 ms 33024 KB Output is correct
18 Correct 1189 ms 32996 KB Output is correct
19 Correct 1258 ms 33124 KB Output is correct
20 Correct 1086 ms 33008 KB Output is correct
21 Correct 1117 ms 33092 KB Output is correct
22 Correct 1124 ms 33048 KB Output is correct
23 Correct 1090 ms 33016 KB Output is correct
24 Correct 1088 ms 33092 KB Output is correct
25 Correct 1376 ms 30472 KB Output is correct
26 Correct 1369 ms 30476 KB Output is correct
27 Correct 1320 ms 32544 KB Output is correct
28 Correct 1235 ms 32940 KB Output is correct
29 Correct 1201 ms 32464 KB Output is correct
30 Correct 1154 ms 32644 KB Output is correct
31 Correct 1219 ms 32988 KB Output is correct
32 Correct 1040 ms 29132 KB Output is correct
33 Correct 0 ms 340 KB Output is correct