Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Sereja and D CodeChef Solution
Problem – Sereja and D CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
<<Previous CodeChef Problem Next Codechef Problem>>
Sereja and D CodeChef Solution in C++17
#include <bits/stdc++.h>
#define sz(x) ll(x.size())
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef pair<ii,ll> tri;
const ll mod=1e9+7;
const ll MAX=1e5+100;
vector<ll> s;
ll spt[22][MAX];
ll lg[MAX];
ll aux;
ll t, d;
ll query(ll l, ll r){
ll ans=max(spt[lg[r-l+1]][l],spt[lg[r-l+1]][r-(1LL<<lg[r-l+1])+1]);
return ans;
}
bool propo(ll x){
return query(aux-x,aux-1)<=d;
}
int main(){
ll n;
cin>>n;
lg[1]=0;
lg[0]=1;
for(ll i=2; i<=n; i++){
lg[i]=lg[i/2]+1;
}
for(ll i=0; i<n; i++){
ll a;
cin>>a;
s.push_back(a);
}
for(ll i=0; i<n-1; i++){
spt[0][i]=s[i+1]-s[i];
}
for(ll i=1; i<=20; i++){
for(ll j=0; j<n-1; j++){
spt[i][j]=spt[i-1][j];
if(j+(1<<(i-1))<n-1) spt[i][j]=max(spt[i][j],spt[i-1][j+(1<<(i-1))]);
}
}
ll q;
cin>>q;
while(q--){
cin>>t>>d;
aux=lower_bound(s.begin(),s.end(),t)-s.begin();
if(aux==sz(s) or s[aux]>t) aux--;
ll lo=0, hi=aux+1;
while(lo+1!=hi){
ll mid=(lo+hi)/2;
if(propo(mid)){
lo=mid;
}
else{
hi=mid;
}
}
cout<<aux-lo+1<<endl;
}
}Sereja and D CodeChef Solution in C++14
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],lo2[100005],st[100005][30],bs[30]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072};
int gm(int l,int r){
if(l>r)return 0;
int k = lo2[r-l+1];
return max(st[l][k],st[r-bs[k]+1][k]);
}
int main(){
scanf("%d",&n);
int nk = 0;
for(int i = 1;i<=100000;i++)lo2[i] = ((bs[nk+1]<=i)?++nk:nk);
for(int i = 1;i<=n;i++)scanf("%d",&a[i]);
for(int i = 1;i<=n;i++)st[i][0] = a[i+1]-a[i];
scanf("%d",&m);
int rz,mxd,nr;
for(int p = 1;bs[p]<=n;p++){
for(int i = 1;i+bs[p]-1<=n;i++){
st[i][p] = max(st[i][p-1],st[i+bs[p-1]][p-1]);
}
}
for(int i = 1;i<=m;i++){
scanf("%d%d",&rz,&mxd);
int l=1,r=n,mid;
while(l<r){
mid = (l+r+1)>>1;
if(a[mid]>rz)r = mid-1;
else l = mid;
}
nr = l;
l = 1;r = nr;
while(l<r){
mid = (l+r)>>1;
if(gm(mid,nr-1)<=mxd)r = mid;
else l = mid+1;
}
printf("%d\n",r);
}
return 0;
} Sereja and D CodeChef Solution in PYTH 3
import sys
from math import *
from bisect import *
MAX = sys.maxsize
MAXN = 10**5+10
logT = [0]*(MAXN)
for i in range(2,MAXN):
logT[i] = logT[i//2]+1
def buildSparse(a):
n = len(a)
k = logT[n]+1
st = [[-MAX for j in range(k)] for i in range(n)]
for i in range(n):
st[i][0] = a[i]
j = 1
while (1<<j)<=n:
i = 0
while (i+(1<<j)-1)<n:
st[i][j] = max(st[i][j-1],st[i+(1<<(j-1))][j-1])
i+=1
j+=1
return st
def query(l,r,st,d):
if l>r:
return False
tot = r-l+1
k = logT[tot]
return max(st[l][k],st[l+tot-(1<<k)][k])<=d
n = int(input())
a = [0]+list(map(int,sys.stdin.readline().strip().split()))
m = int(input())
dif = [0]*(n+1)
for i in range(1,n):
dif[i] = a[i+1]-a[i]
st = buildSparse(dif)
for _ in range(m):
t,d = map(int,sys.stdin.readline().strip().split())
idx = bisect(a,t)-1
lo = 1
hi = idx-1
if idx==1 or a[idx]-a[idx-1]>d:
ans=idx
else:
while lo<hi:
mid = (lo+hi)//2
if query(mid,idx-1,st,d):
hi = mid
else:
lo = mid+1
ans = lo
print(ans)Sereja and D CodeChef Solution in C
#include<stdio.h>
int lower_bound(int vec[],int high, int t)
{
int l=0,mid;
while(high>=l)
{
mid=(l+high)/2;
if(vec[mid]>=t) high=mid-1;
else l=mid+1;
}
return l;
}
int main()
{
int vec[100005];
int n,m,i,j,k,r,x;
scanf("%d",&n);
for(x=0;x<n;x++)
{
scanf("%d",&vec[x]);
}
scanf("%d",&m);
for(j=0;j<m;j++)
{
int t,d;
scanf("%d%d",&t,&d);
i=lower_bound(vec,n-1,t);
if(i>=n || vec[i]>t) --i;
while(i>0 && vec[i-1]+d>=vec[i])
{
k=lower_bound(vec,i-1,vec[i]-d);
i=k;
}
printf("%d\n",i+1);
}
return 0;
}Sereja and D CodeChef Solution in JAVA
/* package codechef; // don't place package name! */
import java.util.*;
import java.io.*;
class E {
static int m[][];
public static void main(String[]args) {
FastReader sc=new FastReader();
int n = sc.nextInt();
int k = 32 - Integer.numberOfLeadingZeros(n);
int a[] = new int[n];
for(int i=0;i<n;i++){
a[i] = sc.nextInt();
}
int b[]= new int[n];
m= new int[k][n];
for(int i=0;i<n-1;i++){
b[i]=a[i+1]-a[i];
m[0][i]=b[i];
}
for(int i=1;1<<i<=n;i++){
for(int j=0;(j-1+(1<<i))<n;j++){
m[i][j]= Math.max(m[i-1][j],m[i-1][j+(1<<(i-1))]);
}
}
int q=sc.nextInt();
while(q-->0){
int t=sc.nextInt(),d=sc.nextInt();
int R = findR(a,t);
System.out.println(findL(R,d)+1);
}
}
private static int findR(int a[],int T){
int R = 0;
int LEFT_BOUND = 1;
int RIGHT_BOUND = a.length-1;
while ( LEFT_BOUND <= RIGHT_BOUND ){
int MID = (LEFT_BOUND + RIGHT_BOUND) / 2;
if ( a[ MID ] <= T ){
R = MID;
LEFT_BOUND = MID + 1;
}else
RIGHT_BOUND = MID - 1;
}
return R;
}
private static int findL(int R,int D){
int L = R;
int LEFT_BOUND = 0;
int RIGHT_BOUND = R - 1;
while ( LEFT_BOUND <= RIGHT_BOUND ){
int MID = (LEFT_BOUND + RIGHT_BOUND) / 2;
if ( G( MID,R,D ) == true ){
L = MID;
RIGHT_BOUND = MID - 1;
}else
LEFT_BOUND = MID + 1;
}
return L;
}
private static boolean G(int L,int R, int D){
int LEFT_BOUND = L;
int RIGHT_BOUND = R - 1; // (we assume, that variable R is global)
int LIMIT = D; // (we assume, that variable D is global too)
int POWER = 31-Integer.numberOfLeadingZeros(RIGHT_BOUND - LEFT_BOUND + 1);
int MAX_VALUE = Math.max( m[ POWER ][ LEFT_BOUND], m[ POWER ][ RIGHT_BOUND - (1<<POWER) + 1 ] );
if ( MAX_VALUE <= LIMIT )
return true;
return false;
}
static class FastReader{
StringTokenizer st=new StringTokenizer("");
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String next() {
while(!st.hasMoreTokens())
try {
st=new StringTokenizer(br.readLine());
}
catch(IOException e){
e.printStackTrace();
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
}
}Sereja and D CodeChef Solution in PYPY 3
import bisect
n=int(input())
arr=[int(c) for c in input().split()]
m=int(input())
for _ in range(m):
t,d=[int(c) for c in input().split()]
oldind=bisect.bisect_right(arr,t)
oldind-=1
t=arr[oldind] - d
newind=oldind
while True:
newind=bisect.bisect_left(arr,t)
# print(newind)
if newind == oldind or newind == 0 :
break
oldind=newind
t=arr[newind] - d
print(newind+1)Sereja and D CodeChef Solution in PYTH
# cook your code here
n = int(raw_input())
s = map(int, raw_input().split())
q = int(raw_input())
diff = [s[i] - s[i-1] for i in xrange(1, n)]
log = [0] * n
for i in xrange(2, n):
log[i] = log[i//2] + 1
k = log[-1]
st = [[float('-inf')] * (k+1) for _ in xrange(n-1)]
for i in xrange(n-1):
st[i][0] = diff[i]
for i in xrange(1, k+1):
for j in xrange(n-1):
if j + (1<<i) <= n-1:
st[j][i] = max(st[j][i-1], st[j + (1 << (i-1)) ][i-1])
def get(l, r):
x = log[r-l+1]
return max(st[l][x], st[r - (1<<x) + 1][x])
from bisect import bisect
for _ in xrange(q):
t, d = map(int, raw_input().split())
p = bisect(s, t) - 1
if p == 0 or diff[p-1] > d:
print p+1
else:
l = 0
r = p-1
while l < r:
mid = l+r>>1
if get(mid, p-1) <=d:
r = mid
else:
l = mid+1
print r+1
Sereja and D CodeChef Solution in GO
# cook your code here
n = int(raw_input())
s = map(int, raw_input().split())
q = int(raw_input())
diff = [s[i] - s[i-1] for i in xrange(1, n)]
log = [0] * n
for i in xrange(2, n):
log[i] = log[i//2] + 1
k = log[-1]
st = [[float('-inf')] * (k+1) for _ in xrange(n-1)]
for i in xrange(n-1):
st[i][0] = diff[i]
for i in xrange(1, k+1):
for j in xrange(n-1):
if j + (1<<i) <= n-1:
st[j][i] = max(st[j][i-1], st[j + (1 << (i-1)) ][i-1])
def get(l, r):
x = log[r-l+1]
return max(st[l][x], st[r - (1<<x) + 1][x])
from bisect import bisect
for _ in xrange(q):
t, d = map(int, raw_input().split())
p = bisect(s, t) - 1
if p == 0 or diff[p-1] > d:
print p+1
else:
l = 0
r = p-1
while l < r:
mid = l+r>>1
if get(mid, p-1) <=d:
r = mid
else:
l = mid+1
print r+1
Sereja and D CodeChef Solution Review:
In our experience, we suggest you solve this Sereja and D CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Sereja and D CodeChef Solution.
Conclusion:
I hope this Sereja and D CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
