oj.uz

Submission #127017

# Submission time Handle Problem Language Result Execution time Memory
127017 2019-07-08T19:43:38 Z hugo_pm Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 897 ms 29304 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 829 ms 26804 KB Output is correct
2 Correct 847 ms 26896 KB Output is correct
3 Correct 832 ms 26804 KB Output is correct
4 Correct 834 ms 26616 KB Output is correct
5 Correct 839 ms 26660 KB Output is correct
6 Correct 835 ms 26744 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 829 ms 26804 KB Output is correct
2 Correct 847 ms 26896 KB Output is correct
3 Correct 832 ms 26804 KB Output is correct
4 Correct 834 ms 26616 KB Output is correct
5 Correct 839 ms 26660 KB Output is correct
6 Correct 835 ms 26744 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 591 ms 25336 KB Output is correct
14 Correct 597 ms 25796 KB Output is correct
15 Correct 573 ms 24416 KB Output is correct
16 Correct 589 ms 25088 KB Output is correct
17 Correct 718 ms 29304 KB Output is correct
18 Correct 723 ms 29304 KB Output is correct
19 Correct 718 ms 29304 KB Output is correct
20 Correct 732 ms 29240 KB Output is correct
21 Correct 723 ms 29176 KB Output is correct
22 Correct 725 ms 29304 KB Output is correct
23 Correct 744 ms 29084 KB Output is correct
24 Correct 735 ms 29284 KB Output is correct
25 Correct 862 ms 26548 KB Output is correct
26 Correct 897 ms 26756 KB Output is correct
27 Correct 763 ms 28920 KB Output is correct
28 Correct 752 ms 29180 KB Output is correct
29 Correct 756 ms 28596 KB Output is correct
30 Correct 782 ms 28740 KB Output is correct
31 Correct 770 ms 28900 KB Output is correct
32 Correct 730 ms 25336 KB Output is correct
33 Correct 2 ms 376 KB Output is correct