# DECOREST - Editorial

Tester: Ritesh Gupta
Editorialist: Ritesh Gupta

SIMPLE

Priority Queue

# PROBLEM:

You are given a sequence p_0, p_1, \ldots, p_{n-1} and a queue. Initially, the queue is empty and each p_i is added in the queue at i_{th} second in the position where all the elements behind it in the queue have less value than this one. Each second i from 0 to n-1, a value gets out the queue who is standing in front of the queue and not added in the i_{th} second. For each valid i, you have to output the time when he comes out of the queue.

# Constraints:

• 1 \le T \le 5
• 1 \le N \le 5 \cdot10^5
• 1 \le A_i \le 10^9 for each valid i

# EXPLANATION:

We can maintain a priority queue which can store elements in descending order. Then for every valid i, we perform the below steps:

1. If the queue is empty then add p_i to the queue.
2. If the queue is not empty and the top-most element of the queue is larger then p_i then -
• Pop-out the top element
• Insert the current element
• Record the time for the top element
1. If the queue is not empty and the top-most element of the queue is lesser than p_i than just insert p_i.

# SOLUTIONS:

Setter's Solution

#include<bits/stdc++.h>
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL)
#define MOD 1000000007
using namespace std;
using ll=long long;

int main()
{
IO;
//freopen(“input.txt”,“r”,stdin);

int t,n;
cin>>t;

while(t--)
{
cin>>n;

map<int,int> m;

vector<int> v(n),ans(n);
for(int i=0;i<n;i++)
{
cin>>v[i];
m[v[i]]=i;
}

set<int> s;

for(int i=0;i<n;i++)
{
if(s.size())
{
int ref=*s.rbegin();

if(ref > v[i])
{
ans[m[ref]]=i;
s.erase(ref);
}
}

s.insert(v[i]);
}

int i=n;

while(s.size())
{
int ref=*s.rbegin();
ans[m[ref]]=i;
s.erase(ref);
i++;
}

for(int i=0;i<n;i++)
cout<<ans[i]<<" ";

cout<<endl;
}


}

Tester's Solution

#include <bits/stdc++.h>

#define endl “\n”

using namespace std;

int a[500010], b[500010];

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int t;
cin >> t;

while(t--)
{
int n;
cin >> n;

for(int i=0;i<n;i++)
cin >> a[i];

set <pair<int,int> > s;
s.insert({a[0],0});
int t = 0;

for(int i=1;i<n;i++)
{
t++;

if((*s.rbegin()).first > a[i])
{
b[(*s.rbegin()).second] = t;
s.erase(--s.end());
}

s.insert({a[i],i});
}

while(!s.empty())
{
t++;
b[(*s.rbegin()).second] = t;
s.erase(--s.end());
}

for(int i=0;i<n;i++)
cout << b[i] << " ";
cout << endl;
}


}

no use of priority_queue in any of the soln (setter/tester) !
what should be the range of the loop ?