Problem link:-problem link
I have been trying this problem for very long time now and i am getting all answers correct for all the test cases that i tried I even tried many test cases from this linktest cases
and getting all correct answer but spoj is giving me wrong answer.
I have used segment trees . I have created struct which stores prefix count (pCount) , suffix count(sCount), prefix Value(pValue) , suffix value(sValue), the total and maxCount .
Can anyone plz check what is wrong with my code or give any test case which fails using this code.
my code:-
`
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include
using namespace std;
#define ll long long int
#define maxn 100005
void _init() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
}
struct node {
int pCount = 1;
int sCount = 1;
int maxCount = 1;
int total = 1;
int pValue;
int sValue;
};
int arr[maxn];
node st[4 * maxn];
void bST(int pos, int low, int high) {
if (low > high)return;
if (low == high) {
st[pos].pCount = 1;
st[pos].sCount = 1;
st[pos].maxCount = 1;
st[pos].total = 1;
st[pos].pValue = arr[low];
st[pos].sValue = arr[low];
return;
}
int mid = (low + high) / 2;
bST(2 * pos + 1, low, mid);
bST(2 * pos + 2, mid + 1, high);
int left = 2 * pos + 1;
int right = 2 * pos + 2;
st[pos].maxCount = max(st[left].maxCount, st[right].maxCount);
if (st[left].sValue == st[right].pValue) st[pos].maxCount = max(st[pos].maxCount, st[left].sCount + st[right].pCount);
if (st[left].pCount == st[left].total && st[left].pValue == st[right].pValue)st[pos].pCount = st[left].total + st[right].pCount;
else st[pos].pCount = st[left].pCount;
if (st[right].sCount == st[right].total && st[right].sValue == st[left].sValue)st[pos].sCount = st[right].total + st[left].sCount;
else st[pos].sCount = st[right].sCount;
st[pos].total = st[left].total + st[right].total;
st[pos].pValue = st[left].pValue;
st[pos].sValue = st[right].sValue;
}
node qST(int pos, int low, int high, int l, int h) {
node temp;
if (l > high || h < low)return temp;
if (low >= l && high <= h)return st[pos];
int mid = (low + high) / 2;
node left = qST(2 * pos + 1, low, mid, l, h);
node right = qST(2 * pos + 2, mid + 1, high, l, h);
temp.maxCount = max(left.maxCount, right.maxCount);
if (left.sValue == right.pValue) temp.maxCount = max(temp.maxCount, left.sCount + right.pCount);
if (left.pCount == left.total && left.pValue == right.pValue)temp.pCount = left.total + right.pCount;
else temp.pCount = left.pCount;
if (right.sCount == right.total && right.sValue == left.sValue)temp.sCount = right.total + left.sCount;
else temp.sCount = right.sCount;
temp.total = left.total + right.total;
temp.pValue = left.pValue;
temp.sValue = right.sValue;
return temp;
}
int main() {
_init();
int n, q;
while (true) {
cin >> n;
if (n == 0)break;
cin >> q;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
bST(0, 0, n - 1);
int l, h;
while (q--) {
cin >> l >> h, l--, h--;
node temp = qST(0, 0, n - 1, l, h);
cout << temp.maxCount << endl;
}
}
return 0;
}
`