oj.uz

Submission #56860

# Submission time Handle Problem Language Result Execution time Memory
56860 2018-07-12T23:48:07 Z ksun48 Worst Reporter 3 (JOI18_worst_reporter3) C++14
19 / 100
 1971 ms 263168 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);
	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 1963 ms 11552 KB Output is correct
2 Correct 1971 ms 17372 KB Output is correct
3 Correct 1954 ms 32932 KB Output is correct
4 Correct 1889 ms 48560 KB Output is correct
5 Correct 1909 ms 63976 KB Output is correct
6 Correct 1788 ms 79436 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1963 ms 11552 KB Output is correct
2 Correct 1971 ms 17372 KB Output is correct
3 Correct 1954 ms 32932 KB Output is correct
4 Correct 1889 ms 48560 KB Output is correct
5 Correct 1909 ms 63976 KB Output is correct
6 Correct 1788 ms 79436 KB Output is correct
7 Correct 4 ms 79436 KB Output is correct
8 Correct 4 ms 79436 KB Output is correct
9 Correct 4 ms 79436 KB Output is correct
10 Correct 7 ms 79436 KB Output is correct
11 Correct 5 ms 79436 KB Output is correct
12 Correct 5 ms 79436 KB Output is correct
13 Correct 1604 ms 93540 KB Output is correct
14 Correct 1785 ms 110136 KB Output is correct
15 Correct 1597 ms 125336 KB Output is correct
16 Correct 1568 ms 140100 KB Output is correct
17 Correct 1820 ms 157996 KB Output is correct
18 Correct 1749 ms 174388 KB Output is correct
19 Correct 1551 ms 191764 KB Output is correct
20 Correct 1712 ms 209080 KB Output is correct
21 Correct 1791 ms 224536 KB Output is correct
22 Correct 1616 ms 239768 KB Output is correct
23 Correct 1750 ms 255064 KB Output is correct
24 Runtime error 1774 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
25 Halted 0 ms 0 KB -