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;
} ~~~~~
Please ignore that bold 'includes'. I'm posting for first time and I tried to edit it but I couldn't do it.
Tip for you, if you want to show your code to the community, try to upload somewhere(for example, ideone or pastebin) or just put these three ``` characters to the front and end of your entire code while writing to the blog, otherwise it is hard to read your code. For instance, here is your code: