oj.uz

Submission #56859

# Submission time Handle Problem Language Result Execution time Memory
56859 2018-07-12T23:47:14 Z ksun48 Worst Reporter 3 (JOI18_worst_reporter3) C++14
12 / 100
 2000 ms 11392 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
vector<LL> d;
vector<LL> jump;
LL where(LL t, LL m){
	LL r = t % jump[m];
	LL curpos = t - r - m - 1;
	return curpos;
}
LL get(LL t, LL pos){
	// at time t how many people are >= pos;
	LL s = -1; // yes
	LL e = d.size(); // no
	while(s + 1 < e){
		LL m = (s + e) / 2;
		// where is person m at certain time. 
		if(where(t,m) >= pos){
			s = m;
		} else {
			e = m;
		}	
	}
	return e + (t >= pos);
}
int main(){
	cin.sync_with_stdio(0);
	LL n;
	LL q;
	cin >> n >> q;
	d.resize(n);
	jump.resize(n);
	LL prev = 1;
	for(int i = 0; i < n; i++){
		cin >> d[i];
		LL numc = (d[i] + prev - 1) / prev;
		jump[i] = prev * numc;
		prev = jump[i];
	}
	for(int i = 0; i < q; i++){
		LL t, l, r;
		cin >> t >> l >> r;
		cout << get(t,l) - get(t,r+1) << '\n';
	}
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2053 ms 11392 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 11392 KB Output is correct
2 Correct 4 ms 11392 KB Output is correct
3 Correct 5 ms 11392 KB Output is correct
4 Correct 5 ms 11392 KB Output is correct
5 Correct 5 ms 11392 KB Output is correct
6 Correct 5 ms 11392 KB Output is correct

Subtask #3
0 / 81.0

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