oj.uz

Submission #156456

# Submission time Handle Problem Language Result Execution time Memory
156456 2019-10-05T19:56:28 Z sofhiasouza Worst Reporter 3 (JOI18_worst_reporter3) C++14
12 / 100
 2000 ms 16984 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e5+10;

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

int main()
{
	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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2021 ms 16984 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2021 ms 16984 KB Time limit exceeded
2 Halted 0 ms 0 KB -