pastebin

Paste Search Dynamic
Recent pastes
wynik
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. pair<int, int> T[1000000];
  4. //int Tkon[1000000];
  5. int main(){
  6.     int n, wynik=0, a,b;
  7.     cin>>n;
  8.     for(int i=0; i<n; i++){
  9.         cin>>T[i].first>>T[i].second;
  10. }
  11.     deque<pair<int, int>> Q; // first to poz second to temp
  12.     for(int i=0; i<n; i++){
  13.         //cout<<Q.size()<<endl;
  14.          a=T[i].first;
  15.          b=T[i].second;
  16.         int naj = i;
  17.         //cout<<a<<' '<<b<<' '<<naj<<endl;
  18.         while(!Q.empty() && Q.front().second <= a){
  19.             naj = min(naj, Q.front().first);
  20.             Q.pop_front();
  21.             //cout<<"k";
  22.         }//cout<<endl;
  23.         pair <int, int>pp;
  24.         pp.first=naj; pp.second=a;
  25.         //cout<<naj<<" "<<a<<endl;
  26.         Q.push_front(pp);
  27.         while(!Q.empty() && Q.back().second > b){ //cout<<"wchodzi"<<endl;
  28.             wynik = max(wynik, i-Q.back().first);
  29.             Q.pop_back();
  30.         }
  31.     }
  32.     while(!Q.empty()){
  33.         wynik = max(wynik, n-Q.back().first);
  34.         Q.pop_back();
  35.     }
  36.     cout<<wynik;
  37.     return 0;
  38. }
  39.  
Parsed in 0.011 seconds