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

Revision en1, by BadeMeow, 2016-07-12 13:20:40

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

include

include

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.

Tags data structures, greedy

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English BadeMeow 2016-07-12 13:25:37 18
en3 English BadeMeow 2016-07-12 13:22:14 172
en2 English BadeMeow 2016-07-12 13:21:48 172
en1 English BadeMeow 2016-07-12 13:20:40 1792 Initial revision (published)