Submission #441871

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
441871	2021-07-06T12:55:45 Z	dutch	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	997 ms	33228 KB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 2e9, MAXN = 5e5;

int n, q, d[MAXN], t[MAXN], s[MAXN];

int search(int x, int p){
	int i = -1;
	for(int j=1<<20; j/=2; ){
		if(i+j >= n) continue;
		i += j;
		if(- i - 1 + x / t[i] * s[i] < p) i -= j;
	}
	return i;
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> q;
	for(int i=0; i<n; ++i) cin >> d[i];

	fill(t, t+n, INF);
	t[0] = s[0] = d[0];

	for(int i=1; i<n; ++i){
		int m = ((d[i] + s[i-1] - 1) / s[i-1]);
		s[i] = m * s[i-1];
		t[i] = m * t[i-1];
		if(t[i] > INF) break;
	}

	while(q--){
		int x, l, r; cin >> x >> l >> r;
		cout << search(x, l) - search(x, r+1) + (l <= x && x <= r) << '\n';
	}
}

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	997 ms	30540 KB	Output is correct
2	Correct	883 ms	30488 KB	Output is correct
3	Correct	877 ms	30580 KB	Output is correct
4	Correct	855 ms	30536 KB	Output is correct
5	Correct	874 ms	30680 KB	Output is correct
6	Correct	917 ms	30608 KB	Output is correct

Subtask #2

12.0 / 12.0

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

Subtask #3

81.0 / 81.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	997 ms	30540 KB	Output is correct
2	Correct	883 ms	30488 KB	Output is correct
3	Correct	877 ms	30580 KB	Output is correct
4	Correct	855 ms	30536 KB	Output is correct
5	Correct	874 ms	30680 KB	Output is correct
6	Correct	917 ms	30608 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	450 ms	28916 KB	Output is correct
14	Correct	468 ms	29660 KB	Output is correct
15	Correct	444 ms	28228 KB	Output is correct
16	Correct	484 ms	28736 KB	Output is correct
17	Correct	604 ms	33228 KB	Output is correct
18	Correct	588 ms	32968 KB	Output is correct
19	Correct	564 ms	33060 KB	Output is correct
20	Correct	553 ms	33044 KB	Output is correct
21	Correct	627 ms	33016 KB	Output is correct
22	Correct	580 ms	33164 KB	Output is correct
23	Correct	578 ms	33028 KB	Output is correct
24	Correct	580 ms	33168 KB	Output is correct
25	Correct	864 ms	30624 KB	Output is correct
26	Correct	896 ms	30532 KB	Output is correct
27	Correct	632 ms	32756 KB	Output is correct
28	Correct	691 ms	32876 KB	Output is correct
29	Correct	651 ms	32716 KB	Output is correct
30	Correct	688 ms	32804 KB	Output is correct
31	Correct	675 ms	32868 KB	Output is correct
32	Correct	629 ms	29184 KB	Output is correct
33	Correct	1 ms	332 KB	Output is correct