Submission #114106

#	Time	Username	Problem	Language	Result	Execution time	Memory
114106		Saboon	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	1961 ms	31424 KiB

worst_reporter3

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int inf = 1e9 + 10;
const int maxn = 5e5 + 10;

ll a[maxn], b[maxn];
int d[maxn];

int myplace(int idx, int time){
	return (time / a[idx]) * b[idx] - idx;
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, Q;
	cin >> n >> Q;
	for (int i = 1; i <= n; i++)
		cin >> d[i];
	// i-th person moves b[i] units forward every a[i] unit of time
	a[1] = b[1] = d[1];
	for (int i = 2; i <= n; i++){
		int lo = 0, hi = inf;
		while (hi - lo > 1){
			int mid = (lo + hi) >> 1;
			if (1ll * mid * b[i - 1] < d[i])
				lo = mid;
			else
				hi = mid; 
		}
		a[i] = 1ll * hi * a[i - 1];
		b[i] = 1ll * hi * b[i - 1];
		// check overflow
	}
	for (int query = 1; query <= Q; query ++){
		int T, L, R;
		cin >> T >> L >> R;
		int lmc, rmc; // leftmost contestant and rightmost contestant
		// find rightmost contestant in picture
		int lo = 0, hi = n + 1;
		while (hi - lo > 1){
			int mid = (lo + hi) >> 1;
			if (myplace(mid, T) >= L)
				lo = mid;
			else
				hi = mid;
		}
		rmc = lo;
		// find leftmost contestant in picture
		lo = 0, hi = n + 1;
		while (hi - lo > 1){
			int mid = (lo + hi) >> 1;
			if (myplace(mid, T) > R)
				lo = mid;
			else
				hi = mid;
		}
		lmc = lo;
		
		bool IOIchan = 0;
		if (L <= T and T <= R)
			IOIchan = 1;
	
		cout << rmc - lmc + IOIchan << '\n';
	}
}

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