Thanks a lot @betlista… got my mistake and finally got AC…
The approach is ingenious in a IOI style contest where partial marks are given.But I think it will get TLE in most judges.
It seems you found the error, right?
Can some one please tell me what wrong i am doing in my code . I am using 2 sparse table
and calculating min and max for each query
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define jaldi_chal ios_base::sync_with_stdio(0); cin.tie(0);
#define MOD 1000000007
#define F first
#define dbg(x) cout<<#x<<" " <<x<<endl;
#define S second
#define inf 1e15
#define endl “\n”
#define setbit(n) __builtin_popcount(n)
#define all(x) x.begin() , x.end()
#define clr(x) memset(x,0,sizeof(x))
ll power(ll a, ll b);
ll a[100007];
ll sp_min[100007][18]; // check for runtime error // min
ll sp_max[100007][18];
int main() {
jaldi_chal
ll t = 1, i;
// cin >> t;
while (t--)
{
ll n;
cin >> n;
for (ll i = 1; i <= n; i++)
{
cin >> a[i];
}
// ll maxN = floor(log2(n));
for (ll i = 1; i <= n; i++)
{
sp_min[i][0] = i;
sp_max[i][0] = i;
}
for (ll j = 1; power(2, j) <= n; j++)
{
for (ll i = 1; i + power(2, j) - 1 <= n; i++)
{
if (a[sp_max[i][j - 1]] > a[sp_max[i + power(2, j - 1)][j - 1]])
{
sp_max[i][j] = sp_max[i][j - 1];
}
else sp_max[i][j] = sp_max[i + power(2, j - 1)][j - 1];
if (a[sp_min[i][j - 1]] < a[sp_min[i + power(2, j - 1)][j - 1]])
{
sp_min[i][j] = sp_min[i][j - 1];
}
else sp_min[i][j] = sp_min[i + power(2, j - 1)][j - 1]; // index based min sparse table
}
}
ll q;
cin >> q;
ll count = 0;
while (q--)
{
ll l, r;
cin >> l >> r;
l++;
r++;
double ans = 0;
ll diff = r - l + 1;
ll val = log2(diff);
ll min_inrange = min(a[sp_min[l][val]], a[sp_min[r - power(2, val) + 1][val]]);
ll max_inrange = max(a[sp_max[l][val]], a[sp_max[r - power(2, val) + 1][val]]);
ll max_out = -inf;
if (l > 1)
{
diff = (l - 1);
val = log2(diff);
max_out = max(max_out, max(a[sp_max[1][val]], a[sp_max[(l - 1) - power(2, val) + 1][val]]));
}
if (r < n)
{
diff = (n - r );
val = log2(diff);
max_out = max(max_out, max(a[sp_max[r + 1][val]], a[sp_max[n - power(2, val) + 1][val]]));
}
cout << setprecision(1) << fixed;
double res = (min_inrange + double(max_inrange - min_inrange) / 2.0);
double outside = min_inrange + max_out;
cout << max(res, outside);
}
}
return 0;
}
ll power(ll a, ll b) {
ll res = 1;
while (b)
{
if (b % 2) b-- , res = res * a;
else b = b / 2 , a *= a;
}
return res;
}
I was solving this problem using segment tree, but getting WA every time. Some please help me with this code CodeChef: Practical coding for everyone I checked many times but unable to figure out what is wrong in this code.
I am solving this problem using two sparse table one for minimum and another for maximum. where i am doing wrong? My solution
Can use Sparse tables here also . Here is my solution if anyone wants to see how to use sparse tables to solve this.
Solution
Can someone please educate me why is my result wrong answer error?
#include <bits/stdc++.h>
using namespace std;
const int N=1e7+1;
int n;
int tmin[N];
int tmax[N];
void buildmax(){
for(int i=n-1;i>0;i–){
tmin[i]=min(tmin[i<<1],tmin[i<<1|1]);
}
}
void buildmin(){
for(int i=n-1;i>0;i–){
tmax[i]=max(tmax[i<<1],tmax[i<<1|1]);
}
}
int qmin(int l,int r){
// [l,r)
int res=1e7+1;
for(l+=n,r+=n;l<r;l>>=1,r>>=1){
if(l&1) res=min(res,tmin[l++]);
if(r&1) res=min(res,tmin[–r]);
}
return res;
}
int qmax(int l,int r){
// [l,r)
int res=-1e7-1;
for(l+=n,r+=n;l<r;l>>=1,r>>=1){
if(l&1) res=max(res,tmax[l++]);
if(r&1) res=max(res,tmax[–r]);
}
return res;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",tmin+n+i);
tmax[n+i]=tmin[n+i];
}
buildmax();
buildmin();
int q,l,r;
scanf("%d",&q);
while(q--){
scanf("%d %d",&l,&r);
double m=qmin(l,r+1);
double M=qmax(l,r+1);
double MM=max(qmax(0,l),qmax(r+1,n));
// cout<<m<<" "<<M<<" "<<MM;
double res;
if(m+(M-m)/2>m+MM){
res=m+(M-m)/2;
}else{
res=m+MM;
}
printf("%.1f",res);
}
return 0;
}
why it is accepting double instead of float
@dhruvpanwar28 Your main idea looks correct. Maybe some small bug in the segment tree implementation. Try once with some standard implementation of segment tree from the internet and then debug yours. emaxx ru has lot of implementation. Just google emaxx ru segment tree.