Submission #127017

#	Time	Username	Problem	Language	Result	Execution time	Memory
127017		hugo_pm	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	897 ms	29304 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

const long long BIG = 1000000000000000000LL;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

void solve();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}

const int borne = 500*1000 + 5;
int nbGens, nbReq;
int sn[borne];
int coeff[borne];

int getPos(int iPer, int tps)
{
	if (iPer == nbGens) return -BIG;
	if (iPer == -1) return BIG;
	int wo = tps / coeff[iPer];
	int pos = wo * coeff[iPer] - iPer - 1;
	return pos;
}

void solve()
{
	cin >> nbGens >> nbReq;

	form(i, nbGens) cin >> sn[i];
	coeff[0] = sn[0];
	form2(i, 1, nbGens) {
		int numer = sn[i];
		int denom = coeff[i-1];
		coeff[i] = (numer+denom-1) / denom;
		coeff[i] *= coeff[i-1];
	}

	form(i, nbReq) {
		int tps, gauche, droite;
		cin >> tps >> gauche >> droite;
		int lo = -1, ri = nbGens;
		while (lo < ri) {
			int mid = (lo+ri+6+1) / 2 - 3;
			int pos = getPos(mid, tps);
			if (pos < gauche) ri = mid-1;
			else lo = mid;
		}

		int borneDr = lo;
		lo = -1; ri = nbGens;
		while (lo < ri) {
			int mid = (lo+ri+6) / 2 - 3;
			int pos = getPos(mid, tps);
			if (pos > droite) lo = mid+1;
			else ri = mid;
		}
		int borneGa = lo;

		if (gauche <= tps && tps <= droite) ++borneDr;

		cout << max(0LL, borneDr-borneGa+1) << "\n";
	}

}

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