답안 #56860

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56860	2018-07-12T23:48:07 Z	ksun48	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	19 / 100	1971 ms	263168 KB

worst_reporter3

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-