For this problem, I have tried to make a solution with ranges. That is to check if the range is valid or not. But I am not able to figure out for what cases it is failing.
#include<bits/stdc++.h>
using namespace std;
const int inf=1000001;
int main()
{
int arr[100000],range[100000][2]; //left right
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>arr[i];
string s;
cin>>s;
if(arr[0]==-1)
{
range[0][0]=0;
range[0][1]=inf;
}
else
{
range[0][0]=range[0][1]=arr[0];
}
for(int i=1;i<n;i++)
{
char c=s[i-1];
if(c=='<')
{
if(arr[i-1]!=-1)
range[i][0]=arr[i-1]+1;
else
range[i][0]=range[i-1][0]+1;
range[i][1]=inf;
}
else if(c=='=')
{
if(arr[i-1]!=-1)
range[i][0]=range[i][1]=arr[i-1];
else
{
range[i][0]=range[i-1][0];
range[i][1]=range[i-1][1];
}
}
else if(c=='>')
{
range[i][0]=0;
if(arr[i-1]!=-1)
range[i][1]=arr[i-1]-1;
else
range[i][1]=range[i-1][1]-1;
}
}
bool ok=true;
for(int i=0;i<n;i++)
{
if(arr[i]==-1)
{
if(range[i][0]>range[i][1])
ok=false;
}
else
{
if(range[i][0]>range[i][1] || arr[i]<range[i][0] || arr[i]>range[i][1] || range[i][1]<0)
ok=false;
}
if(!ok)
{
break;
}
}
if(ok)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}