oj.uz

Submission #774987

# Submission time Handle Problem Language Result Execution time Memory
774987 2023-07-06T06:34:32 Z nhphan0505 Worst Reporter 3 (JOI18_worst_reporter3) C++17
12 / 100
 34 ms 16716 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pii;
#define fi first
#define se second
#define gcd __gcd
#define endl '\n'
const int N=500050,M=1000000007;
const ll INF=0x3f3f3f3f3f3f3f3f;

ll n, q, d[N], u[N], t, l, r;

ll pos(ll i, ll t){return t/u[i]*u[i]-i;}

ll lower(ll t, ll x){
	ll l=-1, r=n+1;
	while(r-l>1){
		ll m=l+r>>1;
		if(pos(m, t)<=x) r=m;
		else l=m;
	}
	return r;
}

ll upper(ll t, ll x){
	ll l=-1, r=n+1;
	while(r-l>1){
		ll m=l+r>>1;
		if(pos(m, t)>=x) l=m;
		else r=m;
	}
	return l;
}

signed main(){
	ios_base::sync_with_stdio(NULL); 
	cin.tie(nullptr); cout.tie(nullptr);
	cin>>n>>q;
	for(ll i=1; i<=n; ++i) cin>>d[i];
	u[0]=1;
	for(ll i=1; i<=n; ++i){
		ll need=(d[i]+u[i-1]-1)/u[i-1];
		u[i]=need*u[i-1];
		// cout<<u[i]<<endl;
	}
	while(q--){
		cin>>t>>l>>r;
		ll up=upper(t, l);
		ll lo=lower(t, r);
		if(pos(lo, t)>=l && pos(lo, t)<=r) cout<<up-lo+1<<endl;
		else cout<<"0\n";
		// cout<<lo<<" "<<up<<endl;
	}
    return 0;
}

Compilation message

worst_reporter3.cpp: In function 'll lower(ll, ll)':
worst_reporter3.cpp:20:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |   ll m=l+r>>1;
      |        ~^~
worst_reporter3.cpp: In function 'll upper(ll, ll)':
worst_reporter3.cpp:30:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |   ll m=l+r>>1;
      |        ~^~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 16716 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

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
0 / 81.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 16716 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -