oj.uz

Submission #56861

# Submission time Handle Problem Language Result Execution time Memory
56861 2018-07-12T23:48:37 Z ksun48 Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 1294 ms 177724 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
vector<LL> d;
vector<LL> jump;

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((t / jump[m]) * jump[m] - m - 1 >= pos){
			s = m;
		} else {
			e = m;
		}	
	}
	return e + (t >= pos);
}
int main(){
	cin.sync_with_stdio(0); cin.tie(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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1182 ms 14316 KB Output is correct
2 Correct 967 ms 20488 KB Output is correct
3 Correct 1276 ms 31612 KB Output is correct
4 Correct 1294 ms 35100 KB Output is correct
5 Correct 1119 ms 42776 KB Output is correct
6 Correct 906 ms 42912 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1182 ms 14316 KB Output is correct
2 Correct 967 ms 20488 KB Output is correct
3 Correct 1276 ms 31612 KB Output is correct
4 Correct 1294 ms 35100 KB Output is correct
5 Correct 1119 ms 42776 KB Output is correct
6 Correct 906 ms 42912 KB Output is correct
7 Correct 4 ms 42912 KB Output is correct
8 Correct 3 ms 42912 KB Output is correct
9 Correct 3 ms 42912 KB Output is correct
10 Correct 3 ms 42912 KB Output is correct
11 Correct 3 ms 42912 KB Output is correct
12 Correct 3 ms 42912 KB Output is correct
13 Correct 581 ms 42912 KB Output is correct
14 Correct 728 ms 42912 KB Output is correct
15 Correct 692 ms 42912 KB Output is correct
16 Correct 950 ms 42912 KB Output is correct
17 Correct 711 ms 42912 KB Output is correct
18 Correct 799 ms 42912 KB Output is correct
19 Correct 745 ms 42912 KB Output is correct
20 Correct 810 ms 42912 KB Output is correct
21 Correct 702 ms 42912 KB Output is correct
22 Correct 688 ms 42912 KB Output is correct
23 Correct 792 ms 42912 KB Output is correct
24 Correct 749 ms 42912 KB Output is correct
25 Correct 1149 ms 58804 KB Output is correct
26 Correct 1241 ms 74240 KB Output is correct
27 Correct 821 ms 91804 KB Output is correct
28 Correct 965 ms 109732 KB Output is correct
29 Correct 742 ms 127564 KB Output is correct
30 Correct 769 ms 145424 KB Output is correct
31 Correct 737 ms 163404 KB Output is correct
32 Correct 718 ms 177724 KB Output is correct
33 Correct 3 ms 177724 KB Output is correct