oj.uz

Submission #286811

# Submission time Handle Problem Language Result Execution time Memory
286811 2020-08-31T03:23:28 Z YJU Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 936 ms 33132 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=5e5+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<62);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()

ll T,L,R,n,q,l[N],d[N],t[N];

ll cal(ll tid,ll range){
	ll ql=-1,qr=n+1;
	while(qr-ql>1){
		ll mid=(ql+qr)/2;
		if(tid/t[mid]*l[mid]-mid>range){
			ql=mid;
		}else{
			qr=mid;
		}
	}
	return (n+1-qr);
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>q;
	l[0]=t[0]=1;
	REP1(i,n)cin>>d[i];
	REP1(i,n){
		l[i]=((d[i]+l[i-1]-1)/l[i-1])*l[i-1];
		t[i]=t[i-1]*((d[i]+l[i-1]-1)/l[i-1]);
		if(t[i]>1e9){n=i;break;}
	}
	while(q--){
		cin>>T>>L>>R;
		//cout<<cal(T,R)<<" "<<cal(T,L-1)<<"\n";
		cout<<cal(T,R)-cal(T,L-1)<<"\n";
	}
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 874 ms 29552 KB Output is correct
2 Correct 912 ms 30812 KB Output is correct
3 Correct 880 ms 30584 KB Output is correct
4 Correct 859 ms 30636 KB Output is correct
5 Correct 867 ms 30656 KB Output is correct
6 Correct 875 ms 30588 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 874 ms 29552 KB Output is correct
2 Correct 912 ms 30812 KB Output is correct
3 Correct 880 ms 30584 KB Output is correct
4 Correct 859 ms 30636 KB Output is correct
5 Correct 867 ms 30656 KB Output is correct
6 Correct 875 ms 30588 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 266 ms 21240 KB Output is correct
14 Correct 276 ms 21752 KB Output is correct
15 Correct 293 ms 20600 KB Output is correct
16 Correct 271 ms 21112 KB Output is correct
17 Correct 546 ms 31096 KB Output is correct
18 Correct 546 ms 30712 KB Output is correct
19 Correct 526 ms 30196 KB Output is correct
20 Correct 537 ms 31548 KB Output is correct
21 Correct 538 ms 30572 KB Output is correct
22 Correct 528 ms 29940 KB Output is correct
23 Correct 550 ms 31608 KB Output is correct
24 Correct 537 ms 30104 KB Output is correct
25 Correct 918 ms 30588 KB Output is correct
26 Correct 936 ms 30700 KB Output is correct
27 Correct 624 ms 32884 KB Output is correct
28 Correct 603 ms 33132 KB Output is correct
29 Correct 583 ms 28088 KB Output is correct
30 Correct 646 ms 29592 KB Output is correct
31 Correct 612 ms 33032 KB Output is correct
32 Correct 636 ms 29148 KB Output is correct
33 Correct 0 ms 384 KB Output is correct