oj.uz

Submission #114106

# Submission time Handle Problem Language Result Execution time Memory
114106 2019-05-30T11:13:43 Z Saboon Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 1961 ms 31424 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1945 ms 28696 KB Output is correct
2 Correct 1839 ms 28708 KB Output is correct
3 Correct 1855 ms 28780 KB Output is correct
4 Correct 1928 ms 28620 KB Output is correct
5 Correct 1895 ms 28724 KB Output is correct
6 Correct 1907 ms 28684 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1945 ms 28696 KB Output is correct
2 Correct 1839 ms 28708 KB Output is correct
3 Correct 1855 ms 28780 KB Output is correct
4 Correct 1928 ms 28620 KB Output is correct
5 Correct 1895 ms 28724 KB Output is correct
6 Correct 1907 ms 28684 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 1318 ms 27340 KB Output is correct
14 Correct 1356 ms 28024 KB Output is correct
15 Correct 1284 ms 26396 KB Output is correct
16 Correct 1276 ms 27016 KB Output is correct
17 Correct 1467 ms 31304 KB Output is correct
18 Correct 1448 ms 31200 KB Output is correct
19 Correct 1457 ms 31404 KB Output is correct
20 Correct 1484 ms 31200 KB Output is correct
21 Correct 1488 ms 31232 KB Output is correct
22 Correct 1504 ms 31364 KB Output is correct
23 Correct 1515 ms 31132 KB Output is correct
24 Correct 1516 ms 31424 KB Output is correct
25 Correct 1961 ms 28500 KB Output is correct
26 Correct 1919 ms 28508 KB Output is correct
27 Correct 1612 ms 30700 KB Output is correct
28 Correct 1516 ms 31176 KB Output is correct
29 Correct 1506 ms 30840 KB Output is correct
30 Correct 1629 ms 30748 KB Output is correct
31 Correct 1536 ms 31008 KB Output is correct
32 Correct 1530 ms 27224 KB Output is correct
33 Correct 2 ms 384 KB Output is correct