oj.uz

Submission #911426

# Submission time Handle Problem Language Result Execution time Memory
911426 2024-01-18T21:54:26 Z amirhoseinfar1385 Worst Reporter 3 (JOI18_worst_reporter3) C++17
19 / 100
 435 ms 24732 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10;
int d[maxn],n,q,dp[maxn],val[maxn];

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

int find(int t,int l){
	int 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(int i=1;i<=n;i++){
		cin>>d[i];
	}
	dp[0]=1;
	val[0]=1;
	for(int 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(int i=0;i<q;i++){
		int t,l,r;
		cin>>t>>l>>r;
		int resr=find(t,r+1),resl=find(t,l);
		int res=resl-resr;
		if(t>=l&&t<=r){
			res++;
		}
		cout<<res<<"\n";
	//	cout<<"hey: "<<l<<" "<<r<<" "<<resl<<" "<<resr<<"\n";
	}
	//for(int i=1;i<=n;i++){
	//	cout<<"wtf: "<<i<<" "<<dp[i]<<" "<<val[i]<<"\n";
	//}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 24732 KB Output is correct
2 Correct 429 ms 24660 KB Output is correct
3 Correct 428 ms 24660 KB Output is correct
4 Correct 433 ms 24692 KB Output is correct
5 Correct 426 ms 24636 KB Output is correct
6 Correct 433 ms 24720 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 24732 KB Output is correct
2 Correct 429 ms 24660 KB Output is correct
3 Correct 428 ms 24660 KB Output is correct
4 Correct 433 ms 24692 KB Output is correct
5 Correct 426 ms 24636 KB Output is correct
6 Correct 433 ms 24720 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Runtime error 52 ms 17056 KB Execution killed with signal 8
14 Halted 0 ms 0 KB -