oj.uz

Submission #156457

# Submission time Handle Problem Language Result Execution time Memory
156457 2019-10-05T19:57:36 Z sofhiasouza Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 640 ms 25276 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e5+10;

int n, q, d[maxn], resp[maxn];

int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

	cin >> n >> q;

	for(int i = 1 ; i <= n ; i++)
	{
		cin >> d[i];
		
		if(d[i-1] > d[i]) resp[i] = resp[i-1];
		else
		{
			if(i == 1)
			{
				resp[i] = d[i];
				//cout << resp[i] << " ";
				continue;
			}
			int aux = d[i]/resp[i-1];
			if(d[i]%resp[i-1]) aux++;

			resp[i] = resp[i-1]*aux;
		}
		//cout << resp[i] << " ";
	}

	//cout << "\n";
	for(int i = 1 ; i <= q ; i++)
	{
		int t, l, r;
		
		cin >> t >> l >> r;

		int ini = 1, fim = n, ans = 0;
		while(ini <= fim)
		{
			int meio = (ini+fim)/2;
			
			int pos = -meio; 
			
			if(t >= resp[meio])
			{
				pos = t/resp[meio];
				//if(resp[meio]%t) pos++;

				pos *= resp[meio];

				pos -= meio;
			}

			//cout << meio << ' ' << pos << "\n";

			if(pos < l) fim = meio-1;
			else if(pos > r) ini = meio+1;
			else
			{
				ans = meio;
				fim = meio-1;
			}
		}

		ini = 1, fim = n;
		int ans2 = 0;
		while(ini <= fim)
		{
			int meio = (ini+fim)/2;
			
			int pos = -meio; 
			
			if(t >= resp[meio])
			{
				pos = t/resp[meio];
				
				pos *= resp[meio];

				pos -= meio;
			}

			if(pos < l) fim = meio-1;
			else if(pos > r) ini = meio+1;
			else
			{
				ans2 = meio;
				ini = meio+1;
			}
		}

		int h = 0;
		if(t >= l and t <= r) h++;

		//cout << ans2 << ' ' << ans << ' ' << h << "\n";

		if(ans2) ans2++;
		cout << (ans2 - ans)+h << "\n";

	}

}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 9404 KB Output is correct
2 Correct 613 ms 20232 KB Output is correct
3 Correct 620 ms 20448 KB Output is correct
4 Correct 640 ms 20204 KB Output is correct
5 Correct 621 ms 20380 KB Output is correct
6 Correct 617 ms 20216 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 9404 KB Output is correct
2 Correct 613 ms 20232 KB Output is correct
3 Correct 620 ms 20448 KB Output is correct
4 Correct 640 ms 20204 KB Output is correct
5 Correct 621 ms 20380 KB Output is correct
6 Correct 617 ms 20216 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 362 ms 18216 KB Output is correct
14 Correct 370 ms 17120 KB Output is correct
15 Correct 343 ms 18056 KB Output is correct
16 Correct 362 ms 18044 KB Output is correct
17 Correct 566 ms 15852 KB Output is correct
18 Correct 543 ms 15876 KB Output is correct
19 Correct 541 ms 15984 KB Output is correct
20 Correct 621 ms 15880 KB Output is correct
21 Correct 548 ms 15824 KB Output is correct
22 Correct 553 ms 25276 KB Output is correct
23 Correct 555 ms 15916 KB Output is correct
24 Correct 544 ms 16040 KB Output is correct
25 Correct 636 ms 20088 KB Output is correct
26 Correct 635 ms 20076 KB Output is correct
27 Correct 574 ms 16348 KB Output is correct
28 Correct 557 ms 16188 KB Output is correct
29 Correct 577 ms 16536 KB Output is correct
30 Correct 573 ms 16248 KB Output is correct
31 Correct 570 ms 25104 KB Output is correct
32 Correct 497 ms 19092 KB Output is correct
33 Correct 2 ms 376 KB Output is correct