Submission #233859

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
233859	2020-05-22T03:13:32 Z	oolimry	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	424 ms	25464 KB

worst_reporter3

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

int arr[500005];
int period[500005];

struct group{ int period, L, R; };
vector<group> G;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int n, q; cin >> n >> q;
	for(int i = 1;i <= n;i++) cin >> arr[i];
	
	period[0] = 1;
	for(int i = 1;i <= n;i++){
		int times = arr[i] / period[i-1];
		if(arr[i] % period[i-1] != 0) times++;
		
		period[i] = times * period[i-1];
	}
	
	int curR = 0;
	
	for(int i = 0;i <= n;i++){
		if(i == n || period[i] != period[i+1]){
			G.push_back({period[i], -i, -curR});
			curR = i+1;
		}
	}
	
	while(q--){
		int t, l, r; cin >> t >> l >> r;
		int ans = 0;
		
		for(group g : G){
			int move = t / g.period;
			int L = g.L + move * g.period;
			int R = g.R + move * g.period;
						
			///l, r are the query range. L, R are the range of people			
			ans += max(0,min({r-l, R-L, R-l, r-L})+1); ///overlap of the 2 ranges
		}
		cout << ans << "\n";
	}
}

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	308 ms	22880 KB	Output is correct
2	Correct	296 ms	22776 KB	Output is correct
3	Correct	300 ms	22956 KB	Output is correct
4	Correct	312 ms	22648 KB	Output is correct
5	Correct	316 ms	22652 KB	Output is correct
6	Correct	308 ms	22776 KB	Output is correct

Subtask #2

12.0 / 12.0

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

Subtask #3

81.0 / 81.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	308 ms	22880 KB	Output is correct
2	Correct	296 ms	22776 KB	Output is correct
3	Correct	300 ms	22956 KB	Output is correct
4	Correct	312 ms	22648 KB	Output is correct
5	Correct	316 ms	22652 KB	Output is correct
6	Correct	308 ms	22776 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	512 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	328 ms	21240 KB	Output is correct
14	Correct	312 ms	21752 KB	Output is correct
15	Correct	298 ms	20472 KB	Output is correct
16	Correct	316 ms	20984 KB	Output is correct
17	Correct	424 ms	25336 KB	Output is correct
18	Correct	402 ms	25312 KB	Output is correct
19	Correct	416 ms	25336 KB	Output is correct
20	Correct	419 ms	25360 KB	Output is correct
21	Correct	409 ms	25208 KB	Output is correct
22	Correct	400 ms	25464 KB	Output is correct
23	Correct	405 ms	25464 KB	Output is correct
24	Correct	414 ms	25336 KB	Output is correct
25	Correct	304 ms	22776 KB	Output is correct
26	Correct	307 ms	22908 KB	Output is correct
27	Correct	402 ms	24824 KB	Output is correct
28	Correct	421 ms	25208 KB	Output is correct
29	Correct	417 ms	24952 KB	Output is correct
30	Correct	415 ms	24824 KB	Output is correct
31	Correct	419 ms	25080 KB	Output is correct
32	Correct	289 ms	21368 KB	Output is correct
33	Correct	4 ms	384 KB	Output is correct