Submission #528839

#	Time	Username	Problem	Language	Result	Execution time	Memory
528839		Leonardo_Paes	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	502 ms	29228 KiB

worst_reporter3

#include<bits/stdc++.h>
using namespace std;
/*
	1o da fila: a cada d1 instantes, anda d1 pra direita
	quando t/d1 * d1 >= d2, d2 gruda em d1

	qtd[i] == qtd de movimentos que IOI-chan tem q andar pra eu andar
	dist[i] == quanto eu ando por andada
	qtd[1] = d1
	dist[1] = d1

	qtd[i] = ((di + dist[i-1] - 1)/dist[i-1]) * qtd[i]; 
	dist[i] =  (qtd[i] / qtd[i-1]) * dist[i-1];
*/

#define int long long

int32_t main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n, q;
	cin >> n >> q;
	vector<int> d(n), qtd(n);
	for(int i=0; i<n; i++){
		cin >> d[i];
		if(i) qtd[i] = ((d[i] + qtd[i-1] - 1)/qtd[i-1]) * qtd[i-1];
		else qtd[i] = d[i];
	}
	while(q--){
		int t, l, r;
		cin >> t >> l >> r;
		int ans = 0;
		if(l <= t and t <= r) ans++;
		// leftmost valid
		int ini = 0, meio, fim = n-1, lans = -1, rans = -1;
		while(ini <= fim){
			meio = (ini + fim) >> 1;
			int pos = t / qtd[meio] * qtd[meio] - meio - 1;
			if(pos <= r){
				lans = meio;
				fim = meio - 1;
			}
			else ini = meio + 1;
		}
		// rightmost valid
		ini = 0, fim = n-1;
		while(ini <= fim){
			meio = (ini + fim) >> 1;
			int pos = t / qtd[meio] * qtd[meio] - meio - 1;
			if(pos >= l){
				rans = meio;
				ini = meio + 1;
			}
			else fim = meio - 1;
		}
		/*for(int i=0; i<n; i++){
			int pos = t / qtd[i] * qtd[i] - i - 1;
			cout << pos << " ";
			if(l <= pos and pos <= r) ans++;
		}
		cout << "\n";
		cout << lans << " " << rans << "\n";*/
		if(lans != -1 and rans != -1 and lans <= rans) ans += rans-lans+1;
		cout << ans << "\n";
	}
	/*vector<int> pos = {0, -1, -2, -3};
	vector<int> d = {1, 1, 5, 11};
	vector<int> qtd(4), dist(4);
	qtd[1] = dist[1] = d[1];
	for(int i=2; i<4; i++){
		//cout << qtd[i-1] << " " << dist[i-1] << "\n";
		qtd[i] = ((d[i] + dist[i-1] - 1)/dist[i-1]) * qtd[i-1]; 
		//dist[i] = (qtd[i] / qtd[i-1]) * dist[i-1];
	}
	for(int i=1; i<4; i++){
		cout << i << " " << qtd[i] << " " << dist[i] << "\n";
	}
	int n = 50;
	for(int t=1; t<=n; t++){
		for(int j=0; j<4; j++){
			if(j == 0) pos[j]++;
			else if(pos[j-1] - pos[j] > d[j]) pos[j] = pos[j-1] - 1;
		}
		cout << "tempo " << t << ": " << pos[1] << " " << pos[2] << " " << pos[3] << "\n";
	}*/
	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 81 / 81