Submission #156456

#	Time	Username	Problem	Language	Result	Execution time	Memory
156456		sofhiasouza	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	12 / 100	2021 ms	16984 KiB

worst_reporter3

#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
• Subtask 2: 12 / 12
• Subtask 3: 0 / 81