I am trying to solve this problem
Chef Ceil has some matchsticks in his kitchen.
Detail of matchsticks:
There are N matchsticks in total. They are numbered from to 0 to N-1 inclusive. All matchsticks have same length. But they may have different rates of burning. For ith matchstick, we denote bi as the time required for that matchstick to completely burn-down if lighted at one end. The matchsticks have uniform rate of burning. If lighted at both ends simultaneously, the matchstick will take only half of the original time to burn down.
Arrangement:
He ties rear end of the all the matchsticks together at one point and the front end is kept free. The matchstick numbered i is adjacent to matchstick numbered i+1 for all 0<= i <=N-2. Bodies of matchsticks do not touch each other, except at rear end. All matchsticks are kept on the floor. Task: There are Q queries, in each query we ask: If he lights the free end of all matchsticks numbered between L and R both inclusive, what will be the time needed for all matchsticks to get completely burnt.
Input:
First line of input contains one integer N, total number of matchsticks. The next line contains N space separated integers bi, where bi is the time required for ith matchstick to completely burn-down if lighted at one end. Next line contains one integer Q, total number of queries you need to answer. Then there are Q queries in next Q lines. Each line has two space separated integers L and R.
Output:
Print Q lines, one for each query, printing the answer for each query, that is, the time it will take for all the matchsticks to get completely burn down. Every time you must print your answer with 1 decimal place.
Constraints:
\$1 <= N <= 105\$
\$1<= bi <= 108\$
\$1 <= Q <= 105\$
\$0 <= L <= R <= N-1\$Examples:
Input - 1 5 1 0 0
Output - 5.0
Input - 2 3 5 1 0 1
Output - 4.0
Input - 18 3 4 2 1 5 7 9 7 10 5 12 3 1 1 2 1 3 2 1 4 10
Output - 9.0
Here is my solution to this problem:
#include <cstdio>
#include <vector>
#include <cmath>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define RANGE_MIN 1
#define RANGE_MAX 2
using namespace std;
typedef vector<int> vi;
typedef vector<int> tl;
vi segment_tree; //tree for finding minimum
vi segment_tree_max; //tree for finding maximum
tl input;
//initialization of the segment trees
void init_segment_tree(int N){
int length = (int)(2 * pow(2.0, floor((log((double)N) / log(2.0)) + 1)));
segment_tree.resize(length,0);
segment_tree_max.resize(length,0);
}
void build_segment_tree(int code,tl A,int node, int b, int e){
if(b==e){
if(code==RANGE_MIN) segment_tree[node] = b;
else segment_tree_max[node] = b;
} else {
int leftIdx = 2*node;
int rightIdx = 2*node + 1;
build_segment_tree(code,A,leftIdx,b,(b+e)/2);
build_segment_tree(code,A,rightIdx,(b+e)/2+1,e);
if(code == RANGE_MIN){
int lContent = segment_tree[leftIdx];
int rContent = segment_tree[rightIdx];
int lValue = A[lContent];
int rValue = A[rContent];
segment_tree[node] = (lValue>rValue) ? rContent : lContent;
} else {
int lContent = segment_tree_max[leftIdx];
int rContent = segment_tree_max[rightIdx];
int lValue = A[lContent];
int rValue = A[rContent];
segment_tree_max[node] = (lValue>rValue) ? lContent : rContent;
}
}
}
int query(int code,tl A, int node, int b,int e,int i,int j){
if(i>e || j<b) return -1;
if(b>=i && e<=j && code == RANGE_MIN) return segment_tree[node];
if(b>=i && e<=j && code == RANGE_MAX) return segment_tree_max[node];
int p1 = query(code,A,2*node,b,(b+e)/2,i,j);
int p2 = query(code,A,2*node + 1, (b+e)/2+1,e,i,j);
if(p1==-1) return p2;
if(p2==-1) return p1;
if(code == RANGE_MIN) return (A[p1]<=A[p2]) ? p1 : p2;
if(code == RANGE_MAX) return (A[p1]<=A[p2]) ? p2 : p1;
}
int main(){
int n,L,R,Q;
int time;
int min,max1,max3;
float max,max2;
scanf("%d",&n);
rep(i,n){
scanf("%d",&time);
input.push_back(time);
}
init_segment_tree(n);
build_segment_tree(1,input,1,0,n-1);
build_segment_tree(2,input,1,0,n-1);
scanf("%d",&Q);
while(Q--){
scanf("%d%d",&L,&R);
min = input[query(1,input,1,0,n-1,L,R)]; //find the minimum in [L,R]
max1 = max3 =0;
if (L>0) max1 = input[query(2,input,1,0,n-1,0,L-1)]; //find the maximum in [0,L-1]
max2 = (float)(input[query(2,input,1,0,n-1,L,R)]-min)/2; //find maximum in [L,R] which is burning twice as fast
if (R<n-1) max3 = input[query(2,input,1,0,n-1,R+1,n-1)]; //find maximum in [R+1,n-1]
max = max1;
if(max2>max) max = max2;
if(max3>max) max = max3;
printf("%0.1f\n",min+max);
}
}
I don't know what's wrong with it, it gets TLE. I implemented the segment tree data as follows:
- \$O(2N)\$ for building 2 segment trees, one to find the minimum and another to find the maximum.
- \$O(4Qlog(N))\$ since I run 4
Range_Min(Max)_querys
for each query \$Q\$.
Everything seems to be working but I still don"t understand why I am getting TLE.