oj.uz

답안 #911427

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
911427 2024-01-18T21:55:11 Z amirhoseinfar1385 Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 481 ms 33284 KB 
#include<bits/stdc++.h>
using namespace std;
const long long maxn=500000+10;
long long d[maxn],n,q,dp[maxn],val[maxn];

bool check(long long t,long long l,long long mid){
	long long ret=(t/dp[mid])*val[mid]-mid;
	//cout<<"wtf: "<<mid<<" "<<ret<<" "<<l<<"\n";
	return ret<l;
}

long long find(long long t,long long l){
	long long low=0,high=n+1,mid;
	while(high-low>1){
		mid=(high+low)>>1;
		if(check(t,l,mid)){
			high=mid;
		}
		else{
			low=mid;
		}
	}
	return high;
} 

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(long long i=1;i<=n;i++){
		cin>>d[i];
	}
	dp[0]=1;
	val[0]=1;
	for(long long i=1;i<=n;i++){
		dp[i]=dp[i-1]*((d[i]+val[i-1]-1)/val[i-1]);
		val[i]=(d[i]+val[i-1]-1)/val[i-1];
		val[i]*=val[i-1];
	}
	for(long long i=0;i<q;i++){
		long long t,l,r;
		cin>>t>>l>>r;
		long long resr=find(t,r+1),resl=find(t,l);
		long long res=resl-resr;
		if(t>=l&&t<=r){
			res++;
		}
		cout<<res<<"\n";
	//	cout<<"hey: "<<l<<" "<<r<<" "<<resl<<" "<<resr<<"\n";
	}
	//for(long long i=1;i<=n;i++){
	//	cout<<"wtf: "<<i<<" "<<dp[i]<<" "<<val[i]<<"\n";
	//}
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 467 ms 15080 KB Output is correct
2 Correct 440 ms 15020 KB Output is correct
3 Correct 441 ms 15144 KB Output is correct
4 Correct 448 ms 15212 KB Output is correct
5 Correct 447 ms 15184 KB Output is correct
6 Correct 481 ms 14980 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 467 ms 15080 KB Output is correct
2 Correct 440 ms 15020 KB Output is correct
3 Correct 441 ms 15144 KB Output is correct
4 Correct 448 ms 15212 KB Output is correct
5 Correct 447 ms 15184 KB Output is correct
6 Correct 481 ms 14980 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4696 KB Output is correct
13 Correct 292 ms 24028 KB Output is correct
14 Correct 313 ms 29988 KB Output is correct
15 Correct 278 ms 28244 KB Output is correct
16 Correct 304 ms 28988 KB Output is correct
17 Correct 347 ms 33024 KB Output is correct
18 Correct 358 ms 33160 KB Output is correct
19 Correct 345 ms 33284 KB Output is correct
20 Correct 364 ms 33052 KB Output is correct
21 Correct 353 ms 33108 KB Output is correct
22 Correct 350 ms 33108 KB Output is correct
23 Correct 357 ms 33044 KB Output is correct
24 Correct 347 ms 33228 KB Output is correct
25 Correct 449 ms 30640 KB Output is correct
26 Correct 454 ms 30672 KB Output is correct
27 Correct 459 ms 32668 KB Output is correct
28 Correct 367 ms 33112 KB Output is correct
29 Correct 386 ms 32768 KB Output is correct
30 Correct 403 ms 32656 KB Output is correct
31 Correct 381 ms 32944 KB Output is correct
32 Correct 380 ms 29256 KB Output is correct
33 Correct 1 ms 4444 KB Output is correct