DECOREST - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Subhadeep Chandra
Tester: Ritesh Gupta
Editorialist: Ritesh Gupta

DIFFICULTY:

SIMPLE

PREREQUISITES:

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;
}

}

2

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

3

setter’s Solution is giving TLE
edit : if we use unordered_map it passes