need help for gss1 problem spoj.

Revision en1, by rushikeshkoli3, 2020-01-07 20:12:25

I am getting WA for below solution. I don't know why. please help me to find the error.

#include<bits/stdc++.h>
using namespace std;

void constructTree(int input[], int segTree[], int low, int high, int pos) {
	if (low == high) {
		segTree[pos] = input[low];
		return;
	}
	int mid = (low + high) / 2;
	constructTree(input, segTree, low, mid, 2 * pos + 1);
	constructTree(input, segTree, mid + 1, high, 2 * pos + 2);
	int temp1 = min(segTree[2 * pos + 1], segTree[2 * pos + 2]);
	int temp2 = max(segTree[2 * pos + 1], segTree[2 * pos + 2]);
	if(temp1 < 0) {
		segTree[pos] = temp2;
	} else {
		segTree[pos] = (segTree[2 * pos + 1] + segTree[2 * pos + 2]);
	}
}

int rangeMaxSum(int segTree[], int qlow, int qhigh, int low, int high, int pos) {
	if(qlow == low && qhigh == high) {
		return segTree[pos];
	}
	if (qlow > high || qhigh < low) {
		return 0;
	}
	int mid = (low + high) / 2;
	int temp1 = rangeMaxSum(segTree, qlow, qhigh, low, mid, 2 * pos + 1);
	int temp2 = rangeMaxSum(segTree, qlow, qhigh, mid + 1, high, 2 * pos + 2);
	if(min(temp1, temp2) < 0){
		return max(temp1, temp2);
	} else {
		return temp1 + temp2;
	}
}

int main() {
	int n, m;
	cin >> n;
	int arr[n];
	for(int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	cin >> m;
	int x, y;
	int segTree[4 * n] = {0};
	constructTree(arr, segTree, 0, n - 1, 0);
	// for(int i = 0; i < 25; i++) {
	// 	cout << segTree[i] << " ";
	// }
	// cout << endl;
	for(int i = 0; i < m; i++) {
		cin >> x >> y;
		int ans = rangeMaxSum(segTree, x - 1, y - 1, 0, n - 1, 0);
		cout << ans << endl;
	}
}

` ~~~~~ Your code here... ~~~~~

`

Tags #segment tree, #spoj, #where wrong

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English rushikeshkoli3 2020-01-07 20:12:25 1694 Initial revision (published)