Submission #233859

#	Time	Username	Problem	Language	Result	Execution time	Memory
233859		oolimry	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	424 ms	25464 KiB

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 / 7
• Subtask 2: 12 / 12
• Subtask 3: 81 / 81