abhijeetgupto - if you process the full city set for every query, you will be doing far too much data handling. Much better to separate out the up-train and down-train cities and then use those either to search for suitable journey start points or pre-process to a time map; something like:
ups = []
downs = [0]
for city, dirn in enumerate(trains, start=1):
if dirn == 1:
ups.append(city)
elif dirn == 2:
downs.append(city)
However: if you hadn’t gotten TLE, you would have gotten WA. The results from a single test case are supposed to be delivered on a single line of space-separated values.
Fast output is as important as fast input in this case - you need to limit your print statements.
Can someone help me find mistake ,I am getting WA
I traversed array left to right for station 1 an then right to left for station 2 to get a minimum distance array named result for each station
time complexity O(n)
#include<iostream>
using namespace std;
int main(void) {
int t;
cin>>t;
while(t--)
{
int cities;
int people;
cin>>cities;
cin>>people;
int a[cities];
int b[people];
int result[cities];
for(int i=0;i<cities;i++)
{
cin>>a[i];
}
for(int i=0;i<people;i++)
{
int destination;
cin>>destination;
b[i]=destination-1;
}
for(int i=0;i<cities;i++)
result[i]=1000000009;
int pos=-1;
for(int i=0;i<cities;i++)
{
if(a[i]==1)
{
pos=i;
}
if(pos!=-1)
{
if(a[i]==2)
result[i]=0;
else
result[i]=min(result[i],i-pos);
}
}
int pos2=-1;
for(int i=cities;i>=0;i--)
{
if(a[i]==2)
{
pos2=i;
}
if(pos2!=-1)
{
if(a[i]==1)
result[i]=0;
else
result[i]=min(result[i],pos2-i);
}
}
for(int i=0;i<people;i++)
{
if(result[b[i]]!=1000000009)
cout<<result[b[i]]<<" ";
else
cout<<-1<<" ";
}
cout<<endl;
}
}
let say if the test case is like this.
6 1
1 2 0 1 2 0
3
now,
I used two multimaps to keep track of stations.
1st map for train numbered 1 and second map for train numbered 2.
so for above test case maps would look like this.
map 1 :
index | train number
1 | 1 (train with number 1 at index 1)
4 | 1 (train with number 1 at index 4)
map 2:
index | train Number
2 | 2
5 | 2
I have ignored the station 0/
now for every query I just need to find the lower_bound of the query
as here q = 3
so I have to find the lower_bound of 3 in map one and the same for map 2
now I have to display the min( (q - lower_bound(3).map1 ) , ( lower_bound(3).map2 - q ) )
