TLE Issue in Codeforces Round #357 (Div. 2) problem C. Heap Operations.

Правка en4, от BadeMeow, 2016-07-12 13:25:37

My code is giving tle on using normal for loop. But, replacing the same with "for(auto& p : ans)" gets the code accpeted.

My code:

#include <iostream>
#include <queue>
#include <string>
 using namespace std;
// struct comparator {
//  bool operator()(int i, int j) {
//  return i > j;
//  }
// };

int main()
{

    // ios_base::sync_with_stdio(false);
    // cin.tie(0);
	int t;
	string ops[] = {"sd","insert","removeMin","getMin"};
	vector <pair<int,int> > v;
	scanf("%d",&t);
	priority_queue<int> minHeap;

	for(int i = 0;i<t;i++)
	{
		string op;
		int x;
		cin >> op;
		//if(op != "removeMin")
		//	cin>>x;

		if(op == "insert")
		{
			cin>>x;
			minHeap.push(-x);
			v.push_back(pair<int,int>(1,x));
		}
		else if(op=="getMin")
		{
			cin>>x;
			while(!minHeap.empty() && -minHeap.top() < x)
			{
				minHeap.pop();
				v.push_back(pair<int,int>(2,0));
			}

			if(minHeap.empty() || -minHeap.top() > x)
			{
				minHeap.push(-x);
				v.push_back(pair<int,int>(1,x));
			}

			v.push_back(pair<int,int>(3,x));
		}
		else 
		{
			if(minHeap.empty())
			{
				v.push_back(pair<int,int>(1,1));
			}
			else
				minHeap.pop();

			v.push_back(pair<int,int>(2,x));
		}
	}

	cout<< v.size()<<endl;

	for(int i = 0;i<v.size();i++)       //this loops gives tle
	{	
		if(v[i].first == 2)
			cout<<ops[v[i].first]<<endl;
		else
			cout<<ops[v[i].first]<<" "<<v[i].second<<endl;
	}

	// for (auto& p : v) {                   //this loops gets accepted
 //        cout << ops[p.first];
 //        if (p.first != 2) {
 //            cout << " " << p.second;
 //        }
 //        cout << "\n";
 //    }

	return 0;
}

Please Help.

Теги data structures, greedy

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский BadeMeow 2016-07-12 13:25:37 18
en3 Английский BadeMeow 2016-07-12 13:22:14 172
en2 Английский BadeMeow 2016-07-12 13:21:48 172
en1 Английский BadeMeow 2016-07-12 13:20:40 1792 Initial revision (published)