oj.uz

답안 #771205

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
771205 2023-07-02T15:26:25 Z Mohammad_Parsa Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 535 ms 33172 KB 
/* in the name of allah */
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pb push_back
#define F first
#define S second
#define mk make_pair
typedef long long ll;

const int N=5e5+7;
ll n,q,d[N],s[N],x[N];

ll pos(int i,ll t){
	return -i+(t/s[i])*x[i];
}

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];
	}
	s[0]=1,x[0]=1;
	for(int i=1;i<=n;i++){
		ll f=d[i]/x[i-1]+(d[i]%x[i-1]!=0);
		s[i]=f*s[i-1];
		x[i]=f*x[i-1];
	}

	while(q--){
		ll t,s,e;
		cin>>t>>s>>e;
		int L,R=0;
		int l=-1,r=n;
		while(r-l>1){
			int m=(l+r)/2;
			if(pos(m,t)<=e)r=m;
			else l=m;
		}
		L=r;
		l=0,r=n+1;
		while(r-l>1){
			int m=(l+r)/2;
			//cout<<m<<endl;
			if(pos(m,t)>=s)l=m;
			else r=m;
		}
		
		R=l;
		if(pos(L,t)>e || pos(R,t)<s)L++;
		
		cout<<R-L+1<<endl;
		//cout<<L<<" "<<R<<endl;
	}
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 497 ms 15020 KB Output is correct
2 Correct 493 ms 30492 KB Output is correct
3 Correct 534 ms 30516 KB Output is correct
4 Correct 500 ms 30512 KB Output is correct
5 Correct 535 ms 30504 KB Output is correct
6 Correct 491 ms 30512 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 497 ms 15020 KB Output is correct
2 Correct 493 ms 30492 KB Output is correct
3 Correct 534 ms 30516 KB Output is correct
4 Correct 500 ms 30512 KB Output is correct
5 Correct 535 ms 30504 KB Output is correct
6 Correct 491 ms 30512 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 357 ms 29004 KB Output is correct
14 Correct 325 ms 29576 KB Output is correct
15 Correct 312 ms 28276 KB Output is correct
16 Correct 319 ms 28780 KB Output is correct
17 Correct 381 ms 33064 KB Output is correct
18 Correct 394 ms 33024 KB Output is correct
19 Correct 377 ms 33172 KB Output is correct
20 Correct 384 ms 32992 KB Output is correct
21 Correct 380 ms 33008 KB Output is correct
22 Correct 383 ms 33108 KB Output is correct
23 Correct 373 ms 32956 KB Output is correct
24 Correct 387 ms 33156 KB Output is correct
25 Correct 495 ms 30540 KB Output is correct
26 Correct 498 ms 30544 KB Output is correct
27 Correct 462 ms 32676 KB Output is correct
28 Correct 404 ms 32920 KB Output is correct
29 Correct 404 ms 32460 KB Output is correct
30 Correct 425 ms 32680 KB Output is correct
31 Correct 410 ms 32848 KB Output is correct
32 Correct 404 ms 29104 KB Output is correct
33 Correct 1 ms 340 KB Output is correct