oj.uz

Submission #528839

# Submission time Handle Problem Language Result Execution time Memory
528839 2022-02-21T14:50:46 Z Leonardo_Paes Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 502 ms 29228 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];
*/

#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 11120 KB Output is correct
2 Correct 502 ms 11036 KB Output is correct
3 Correct 494 ms 11152 KB Output is correct
4 Correct 496 ms 11236 KB Output is correct
5 Correct 491 ms 11204 KB Output is correct
6 Correct 465 ms 11112 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 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 11120 KB Output is correct
2 Correct 502 ms 11036 KB Output is correct
3 Correct 494 ms 11152 KB Output is correct
4 Correct 496 ms 11236 KB Output is correct
5 Correct 491 ms 11204 KB Output is correct
6 Correct 465 ms 11112 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 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 308 ms 24984 KB Output is correct
14 Correct 307 ms 25620 KB Output is correct
15 Correct 295 ms 24328 KB Output is correct
16 Correct 292 ms 24884 KB Output is correct
17 Correct 379 ms 29124 KB Output is correct
18 Correct 378 ms 29036 KB Output is correct
19 Correct 379 ms 29200 KB Output is correct
20 Correct 377 ms 29104 KB Output is correct
21 Correct 387 ms 29092 KB Output is correct
22 Correct 402 ms 29212 KB Output is correct
23 Correct 394 ms 29040 KB Output is correct
24 Correct 385 ms 29228 KB Output is correct
25 Correct 488 ms 26596 KB Output is correct
26 Correct 498 ms 26564 KB Output is correct
27 Correct 454 ms 28648 KB Output is correct
28 Correct 426 ms 28992 KB Output is correct
29 Correct 426 ms 28596 KB Output is correct
30 Correct 421 ms 28716 KB Output is correct
31 Correct 449 ms 27292 KB Output is correct
32 Correct 386 ms 25116 KB Output is correct
33 Correct 1 ms 204 KB Output is correct