oj.uz

Submission #627076

# Submission time Handle Problem Language Result Execution time Memory
627076 2022-08-12T06:37:45 Z codr0 Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 583 ms 7280 KB 
// Code by Parsa Eslami

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>

#define err(x) cerr<#x<<" : "<<x<<'\n'
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second
#define pb push_back
#define bit(i,j) ((j>>i)&1)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define all(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define dmid int mid=(r+l)/2
#define lc 2*id
#define rc 2*id+1

using namespace std;
const int N=5e5+4;
int r[N],d[N];
int n;

	int pos(int x,int t){
		return (-x+(t/r[x])*d[x]);
	}

	int32_t main(){
	iostream::sync_with_stdio(0); cin.tie(0);

	int q;
	cin>>n>>q;
	d[0]=1; r[0]=1;
	FOR(i,1,n) cin>>d[i];
	FOR(i,1,n){
		if(r[i-1]>1e9){ r[i]=2e9; continue;}
		/*if(d[i-1]==0){
			cout<<i<<'\n';
			FOR(j,0,i) cout<<d[j]<<" ";
			cout<<'\n';
			exit(0);
		}*/
		ll x=d[i]/d[i-1];
		if(d[i]%d[i-1]!=0) x++;
		/*if(x==0){
			cout<<i<<"&\n";
		}*/
		d[i]=x*d[i-1];
		x=x*r[i-1];
		if(x>1e9) r[i]=2e9;
		else r[i]=x;
	}
	/*FOR(i,0,n) cout<<r[i]<<" ";
	cout<<'\n';
	FOR(i,0,n) cout<<d[i]<<" ";
	cout<<'\n';*/
	FOR(i,1,q){
		int t,l,rr; cin>>t>>l>>rr;
		int ans=0;
		int L=-1,R=n+1;
		while(R-L>1){
			int mid=(R+L)/2;
			if(pos(mid,t)<=rr) R=mid;
			else L=mid;
		}
		ans+=(n+1-R);
		L=-1,R=n+1;
		while(R-L>1){
			int mid=(R+L)/2;
			if(pos(mid,t)<l) R=mid;
			else L=mid;
		}
		ans-=(n+1-R);
		cout<<ans<<'\n';
	}

	return 0;
	}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 7280 KB Output is correct
2 Correct 552 ms 7188 KB Output is correct
3 Correct 571 ms 7124 KB Output is correct
4 Correct 539 ms 7116 KB Output is correct
5 Correct 554 ms 7188 KB Output is correct
6 Correct 583 ms 7164 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 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

# Verdict Execution time Memory Grader output
1 Correct 534 ms 7280 KB Output is correct
2 Correct 552 ms 7188 KB Output is correct
3 Correct 571 ms 7124 KB Output is correct
4 Correct 539 ms 7116 KB Output is correct
5 Correct 554 ms 7188 KB Output is correct
6 Correct 583 ms 7164 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 340 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 377 ms 5192 KB Output is correct
14 Correct 369 ms 5160 KB Output is correct
15 Correct 358 ms 5196 KB Output is correct
16 Correct 362 ms 5216 KB Output is correct
17 Correct 439 ms 6532 KB Output is correct
18 Correct 457 ms 6620 KB Output is correct
19 Correct 443 ms 6556 KB Output is correct
20 Correct 437 ms 6576 KB Output is correct
21 Correct 454 ms 6552 KB Output is correct
22 Correct 416 ms 6576 KB Output is correct
23 Correct 419 ms 6648 KB Output is correct
24 Correct 418 ms 6588 KB Output is correct
25 Correct 559 ms 7164 KB Output is correct
26 Correct 568 ms 7144 KB Output is correct
27 Correct 500 ms 7180 KB Output is correct
28 Correct 454 ms 7100 KB Output is correct
29 Correct 442 ms 6940 KB Output is correct
30 Correct 485 ms 7068 KB Output is correct
31 Correct 472 ms 6964 KB Output is correct
32 Correct 494 ms 6628 KB Output is correct
33 Correct 0 ms 212 KB Output is correct