oj.uz

Submission #49242

# Submission time Handle Problem Language Result Execution time Memory
49242 2018-05-24T02:00:44 Z spencercompton Worst Reporter 3 (JOI18_worst_reporter3) C++17
12 / 100
 2000 ms 23364 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;
	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";
	}
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2075 ms 23364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2075 ms 23364 KB Time limit exceeded
2 Halted 0 ms 0 KB -