Question- Nastya is buying lunch 1136D
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;
} ~~~~~