oj.uz

답안 #56858

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
56858 2018-07-12T23:45:51 Z ksun48 Worst Reporter 3 (JOI18_worst_reporter3) C++14
12 / 100
 2000 ms 41336 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. 
		LL curpos = where(t,m);
		if(curpos >= 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1799 ms 26716 KB Output is correct
2 Execution timed out 2040 ms 41336 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 41336 KB Output is correct
2 Correct 4 ms 41336 KB Output is correct
3 Correct 5 ms 41336 KB Output is correct
4 Correct 5 ms 41336 KB Output is correct
5 Correct 4 ms 41336 KB Output is correct
6 Correct 5 ms 41336 KB Output is correct

Subtask #3
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1799 ms 26716 KB Output is correct
2 Execution timed out 2040 ms 41336 KB Time limit exceeded
3 Halted 0 ms 0 KB -