PROBLEM LINK:
Author: Vishal
Tester: Vishal
Editorialist: Vishal
DIFFICULTY:
EASY
PREREQUISITES:
Stack
PROBLEM:
Given a bunch of operations, you have to either add an element to a stack, or remove the topmost element. Then you have to answer queries on whether two elements were ever present in the stack at the same time.
EXPLANATION:
The idea is to keep track of when each element was added and when each element was removed, i.e the In-times and the Out-times.
Each time we add an element, we update its In-time, that is, the time at which it was added. Similarly, when we remove an element, we update its Out-time, that is, the time at which it was removed. Here, time indicates the index of the operations array.
Now, to answer query, we first check if both elements were ever added onto the stack.
If either element was never added, just print “NO”.
Otherwise, now, two elements x and y were only present together in the stack at some point if:
(in[x]<in[y] and out[x]>out[y]) OR (in[y]<in[x] and out[y]>out[x])
That is, x and y were together only if x was added before y and removed after y, or the other way round.
Since each query is answered in constant time, Time complexity : O(N + Q)
SOLUTION:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9; //Set Infinity as some large value
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int tt=1;
cin>>tt;
while(tt--)
{
int n;
cin>>n;
int in[n+1],out[n+1];
for(int i=0;i<=n;++i)
in[i] = out[i] = INF; //Make in and outtimes Infinity initially
stack<int> s;
for(int i=0;i<n;++i)
{
int x;
cin>>x;
if(x==0)
{
out[s.top()] = i; //Update outtime while removing
s.pop();
}
else
{
in[x] = i; //Update intime while adding
s.push(x);
}
}
int q;
cin>>q;
while(q--)
{
int x,y;
cin>>x>>y;
if(in[x]==INF || in[y]==INF) //Intime = INF means item was never added
{
cout<<"NO\n";
continue;
}
if((in[x]<=in[y] && out[x]>=out[y]) || (in[y]<=in[x] && out[y]>=out[x]))
cout<<"YES\n";
else cout<<"NO\n";
}
}
}