Submission #49243

# Submission time Handle Problem Language Result Execution time Memory
49243 2018-05-24T02:01:59 Z spencercompton Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
1473 ms 262144 KB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll get(ll tim, ll ind, ll wait, ll m){
	return tim/wait * m - ind;
}
int main(){
	int n, q;
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> q;
	ll d[n+1];
	ll x[n+1];
	ll mov[n+1];
	d[0] = 1LL;
	x[0] = 1LL;
	mov[0] = 1LL;
	for(int i = 1; i<=n; i++){
		cin >> d[i];
		x[i] = (d[i]/mov[i-1])*x[i-1];
		if(d[i]%mov[i-1]!=0){
			x[i] += x[i-1];
		}
		mov[i] = x[i]/x[i-1]*mov[i-1];
	}
	for(int i = 0; i<q; i++){
		ll t, l, r;
		cin >> t >> l >> r;
		//binsearch for first person in range
		int lo = 0;
		int hi = n;
		while(lo<hi){
			int mid = (lo+hi)/2;
			if(get(t,mid,x[mid],mov[mid])<=r){
				hi = mid;
			}
			else{
				lo = mid+1;
			}
		}
		if(get(t,lo,x[lo],mov[lo])<l || get(t,lo,x[lo],mov[lo])>r){
			cout << 0 << "\n";
			continue;
		}
		int og = lo;
		lo = 0;
		hi = n;
		while(lo<hi){
			int mid = (lo+hi+1)/2;
			if(get(t,mid,x[mid],mov[mid])>=l){
				lo = mid;
			}
			else{
				hi = mid-1;
			}
		}
		cout << (hi-og+1) << "\n";
	}
}
# Verdict Execution time Memory Grader output
1 Correct 1300 ms 21356 KB Output is correct
2 Correct 1421 ms 36920 KB Output is correct
3 Correct 1155 ms 52132 KB Output is correct
4 Correct 1222 ms 67780 KB Output is correct
5 Correct 1307 ms 83372 KB Output is correct
6 Correct 1473 ms 98812 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 98812 KB Output is correct
2 Correct 3 ms 98812 KB Output is correct
3 Correct 3 ms 98812 KB Output is correct
4 Correct 3 ms 98812 KB Output is correct
5 Correct 4 ms 98812 KB Output is correct
6 Correct 3 ms 98812 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1300 ms 21356 KB Output is correct
2 Correct 1421 ms 36920 KB Output is correct
3 Correct 1155 ms 52132 KB Output is correct
4 Correct 1222 ms 67780 KB Output is correct
5 Correct 1307 ms 83372 KB Output is correct
6 Correct 1473 ms 98812 KB Output is correct
7 Correct 3 ms 98812 KB Output is correct
8 Correct 3 ms 98812 KB Output is correct
9 Correct 3 ms 98812 KB Output is correct
10 Correct 3 ms 98812 KB Output is correct
11 Correct 4 ms 98812 KB Output is correct
12 Correct 3 ms 98812 KB Output is correct
13 Correct 687 ms 112964 KB Output is correct
14 Correct 745 ms 129480 KB Output is correct
15 Correct 567 ms 144772 KB Output is correct
16 Correct 569 ms 160516 KB Output is correct
17 Correct 852 ms 180524 KB Output is correct
18 Correct 947 ms 199248 KB Output is correct
19 Correct 978 ms 217984 KB Output is correct
20 Correct 889 ms 236708 KB Output is correct
21 Correct 945 ms 255220 KB Output is correct
22 Correct 719 ms 262144 KB Output is correct
23 Correct 816 ms 262144 KB Output is correct
24 Correct 894 ms 262144 KB Output is correct
25 Correct 1010 ms 262144 KB Output is correct
26 Correct 1025 ms 262144 KB Output is correct
27 Correct 1076 ms 262144 KB Output is correct
28 Correct 1205 ms 262144 KB Output is correct
29 Correct 934 ms 262144 KB Output is correct
30 Correct 1012 ms 262144 KB Output is correct
31 Correct 980 ms 262144 KB Output is correct
32 Correct 888 ms 262144 KB Output is correct
33 Correct 3 ms 262144 KB Output is correct