My approach for this question is similar to it's solution 1 of the editorial, but my submission is giving TLE. In my code, I focused only on the pupil who can let Natya swap with them. So I kept a track of their position and iterated on all of such pupil to see whether they can actually let Natya advance by advancing all pupil who are between them and Natya. I feel solution 1 to this problem is also similar but I don't know why my solution gives TLE. Also I don't get how the complexity of this solution is O(n+m).
Here is my code-
include
include
include
using namespace std;
int a[300000],b[500000]={0};
map<pair<int,int>,int> mymap;
map<int,int> pos;
void swap(int i,int j) { int temp; temp=a[i]; a[i]=a[j]; a[j]=temp; }
int main() { int n,m,x,y,j=0; cin>>n>>m; for(int i=0;i<n;i++) { cin>>a[i]; } for(int i=0;i<m;i++) { cin>>x>>y; mymap[{x,y}]=1;
}
for(int i=0;i<n;i++)
{
if(mymap[{a[i],a[n-1]}]==1)
{
b[j]=a[i];
j++;
pos[a[i]]=i;
}
}
j--;
int nastya=a[n-1],i;
while(j>=0)
{
for(i=pos[b[j]];a[i+1]!=nastya;i++)
{
if(mymap[{a[i],a[i+1]}]==1)
swap(i,i+1);
else
break;
}
if(a[i+1]==nastya)
{
if(mymap[{a[i],a[i+1]}]==1)
swap(i,i+1);
}
j--;
}
for(i=0;i<n;i++)
{
if(a[i]==nastya)
break;
}
cout<<n-1-i<<endl;
}