Submission #70892

#	Time	Username	Problem	Language	Result	Execution time	Memory
70892		AlphaRazra	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	12 / 100	2044 ms	21624 KiB

worst_reporter3

#include<bits/stdc++.h>
#define mp make_pair
#define fs first
#define sc second
#define pb push_back
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define mod 998244353
#define INF 1e18
using namespace std;

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
* if you have no idea just guess the appropriate well-known algo instead of doing nothing :/
*/

int n,q;
long long a[500005];
long long mov[500005];
long long t,l,r;

bool cek(long long dist,int idx){
	long long nyak = t / mov[idx];
	nyak = nyak * mov[idx];

	nyak = nyak - idx;
	if(nyak <= dist){
		return true;
	}
	return false;
}

int main(){
	cin >> n >> q;

	mov[0] = 1;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		long long nyak = a[i] / mov[i - 1];
		if(a[i] % mov[i - 1] != 0){
			nyak++;
		}
		mov[i] = mov[i - 1] * nyak;
	//	cout << i << " " << mov[i] << " here\n";
	}

	for(int i = 1; i <= q; i++){
		cin >> t >> l >> r;
		int kiri,kanan,ansL,ansR;

		l--;
		kiri = 1, kanan = n;
		ansL = n + 1;
		while(kiri <= kanan){
			int mid = (kiri + kanan) / 2;

			if(cek(l,mid)){
				ansL = mid;
				kanan = mid - 1;
			}else{
				kiri = mid + 1;
			}
		}
		kiri = 1; kanan = n;
		ansR = n + 1;
		while(kiri <= kanan){
			int mid = (kiri + kanan) / 2;

			if(cek(r,mid)){
				ansR = mid;
				kanan = mid - 1;
			}else{
				kiri = mid + 1;
			}
		}
		int tamb = 0;
		if(t > l && t <= r) tamb = 1;
		cout << ansL - ansR + tamb << "\n";
	}
}

• Subtask 1: 0 / 7
• Subtask 2: 12 / 12
• Subtask 3: 0 / 81