oj.uz

Submission #528838

# Submission time Handle Problem Language Result Execution time Memory
528838 2022-02-21T14:49:13 Z Leonardo_Paes Worst Reporter 3 (JOI18_worst_reporter3) C++17
19 / 100
 478 ms 22840 KB 
#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];
*/
int 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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 10820 KB Output is correct
2 Correct 470 ms 22636 KB Output is correct
3 Correct 475 ms 22668 KB Output is correct
4 Correct 466 ms 22608 KB Output is correct
5 Correct 470 ms 22840 KB Output is correct
6 Correct 478 ms 22672 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 10820 KB Output is correct
2 Correct 470 ms 22636 KB Output is correct
3 Correct 475 ms 22668 KB Output is correct
4 Correct 466 ms 22608 KB Output is correct
5 Correct 470 ms 22840 KB Output is correct
6 Correct 478 ms 22672 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Runtime error 6 ms 8440 KB Execution killed with signal 8
14 Halted 0 ms 0 KB -