Submission #46781

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
46781	2018-04-23T08:45:43 Z	kyleliu	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	1813 ms	194868 KB

worst_reporter3

#include <bits/stdc++.h> // PLEASE

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pp;
#define MAXN 500005
#define MAXM 1005
#define MAXP 25
#define A first
#define B second
#define MP make_pair
#define PB push_back
const ll INF = 2e9+13;
const ll MOD = 1e9+7;

int N, Q;
ll D[MAXN];
ll calc(ll a, ll b)
{
	ll x = a/b;
	while(b * x < a) ++x;
	return x;
}

int get(ll T, ll x)
{
	int l=0; int r = N; int ret = -1;
	while(l <= r) {
		int md = (l+r)/2;
		if(x <= (T/D[md]) * D[md] - 1LL*md) {
			ret = md;
			l=md+1;
		}
		else r=md-1;
	}
	return ret;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> Q;
	D[0] = 1;
	for(int i=1; i<=N; i++) cin >> D[i];	
	for(int i=1; i<=N; i++) D[i] = D[i-1] * calc(D[i], D[i-1]);
	
	while(Q--) {
		ll lq, rq, t;
		cin >> t >> lq >> rq;
		
		cout << get(t, lq) - get(t, rq+1) << endl;
	}
	
			
}

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1691 ms	22148 KB	Output is correct
2	Correct	1701 ms	37548 KB	Output is correct
3	Correct	1650 ms	53064 KB	Output is correct
4	Correct	1730 ms	68488 KB	Output is correct
5	Correct	1699 ms	83848 KB	Output is correct
6	Correct	1813 ms	99296 KB	Output is correct

Subtask #2

12.0 / 12.0

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

Subtask #3

81.0 / 81.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1691 ms	22148 KB	Output is correct
2	Correct	1701 ms	37548 KB	Output is correct
3	Correct	1650 ms	53064 KB	Output is correct
4	Correct	1730 ms	68488 KB	Output is correct
5	Correct	1699 ms	83848 KB	Output is correct
6	Correct	1813 ms	99296 KB	Output is correct
7	Correct	4 ms	99296 KB	Output is correct
8	Correct	4 ms	99296 KB	Output is correct
9	Correct	4 ms	99296 KB	Output is correct
10	Correct	20 ms	99296 KB	Output is correct
11	Correct	4 ms	99296 KB	Output is correct
12	Correct	4 ms	99296 KB	Output is correct
13	Correct	1273 ms	113480 KB	Output is correct
14	Correct	1350 ms	130016 KB	Output is correct
15	Correct	1249 ms	145384 KB	Output is correct
16	Correct	1307 ms	160936 KB	Output is correct
17	Correct	1415 ms	180904 KB	Output is correct
18	Correct	1417 ms	194272 KB	Output is correct
19	Correct	1438 ms	194272 KB	Output is correct
20	Correct	1411 ms	194356 KB	Output is correct
21	Correct	1464 ms	194356 KB	Output is correct
22	Correct	1427 ms	194356 KB	Output is correct
23	Correct	1450 ms	194356 KB	Output is correct
24	Correct	1432 ms	194356 KB	Output is correct
25	Correct	1751 ms	194868 KB	Output is correct
26	Correct	1773 ms	194868 KB	Output is correct
27	Correct	1502 ms	194868 KB	Output is correct
28	Correct	1463 ms	194868 KB	Output is correct
29	Correct	1426 ms	194868 KB	Output is correct
30	Correct	1486 ms	194868 KB	Output is correct
31	Correct	1477 ms	194868 KB	Output is correct
32	Correct	1552 ms	194868 KB	Output is correct
33	Correct	2 ms	194868 KB	Output is correct