https://codeforces.com/condest/1435/submission/967576666 - & gt ; Używane set.upper_bound () https://codeforces.com/condest/1435/submission/96761788 - & gt ; Używane Upper_bound (Set.begin (), set.end ())

Zauważyłem, że set.upper_bound () był szybszy niż ten ostatni (ten ostatni dał limit czasu). Dlaczego?

Kod poniżej daje przekroczony limit czasu

int ind = * Upper_bound (St.begin (), St.end (), MP [I], większa ());

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
# define ll  long long int
# define ld  long double
# define pb push_back
# define pp pop_back
# define ff first
# define ss second
# define mp make_pair
typedef priority_queue<ll, vector<ll>, greater<ll>> minheap;
typedef priority_queue<ll> maxheap;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void solve(){
    int n;
      cin>>n;
      set<int, greater<int>>st;
      st.insert(-1);
      map<int,int> mp;
      int p[2*n];
      char s[2*n];
        for(int i=0;i<2*n;i++)
      {
          cin>>s[i];
          if(s[i]=='+')
          st.insert(i);
          else
          {
              cin>>p[i];
              mp[p[i]]=i;
          }
     
      }
      for(int i=1;i<=n;i++)
      {
        
          int ind = *upper_bound(st.begin(), st.end(), mp[i], greater< int>());
          if(ind==-1||st.find(ind)==st.end())
          {
              // if (-) come before +
              cout<<"NO\n";
              return;
          }
          st.erase(ind);
          p[ind] = i;
          
      }
     
    // cout<<endl;
    stack<int>stc;
    for(int i=0;i<2*n;i++)
    {
        if(s[i]=='+')
        stc.push(p[i]);
        else
        {
            if(stc.top()==p[i])
            stc.pop();
            else
            {
                //if element not in order given in language
                cout<<"NO\n";
                return ;
            }
        }
    }
    cout<<"YES\n";
    for(int i=0;i<2*n;i++)
    {
        if(s[i]=='+')
        cout<<p[i]<<endl;
    }
    return;
}   


int  main()
{
    #ifndef ONLINE_JUDGE
       freopen("input.txt", "r", stdin);
       freopen("output.txt", "w", stdout);
    #endif
      IOS
     int t = 1;
     //cin >> t;
     while(t--){
        solve();
     }
    return 0;
}

Ten sam kod z "set.upper_bound ()" Ustalono w terminie.

int ind = * st.upper_bound (mp [i]);

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
# define ll  long long int
# define ld  long double
# define pb push_back
# define pp pop_back
# define ff first
# define ss second
# define mp make_pair
typedef priority_queue<ll, vector<ll>, greater<ll>> minheap;
typedef priority_queue<ll> maxheap;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void solve(){
    int n;
      cin>>n;
      set<int, greater<int>>st;
      st.insert(-1);
      map<int,int> mp;
      int p[2*n];
      char s[2*n];
        for(int i=0;i<2*n;i++)
      {
          cin>>s[i];
          if(s[i]=='+')
          st.insert(i);
          else
          {
              cin>>p[i];
              mp[p[i]]=i;
          }
     
      }
      for(int i=1;i<=n;i++)
      {
        
          int ind = *st.upper_bound(mp[i]);
          if(ind==-1||st.find(ind)==st.end())
          {
              // if (-) come before +
              cout<<"NO\n";
              return;
          }
          st.erase(ind);
          p[ind] = i;
          
      }
     
    // cout<<endl;
    stack<int>stc;
    for(int i=0;i<2*n;i++)
    {
        if(s[i]=='+')
        stc.push(p[i]);
        else
        {
            if(stc.top()==p[i])
            stc.pop();
            else
            {
                //if element not in order given in language
                cout<<"NO\n";
                return ;
            }
        }
    }
    cout<<"YES\n";
    for(int i=0;i<2*n;i++)
    {
        if(s[i]=='+')
        cout<<p[i]<<endl;
    }
    return;
}   


int  main()
{
    #ifndef ONLINE_JUDGE
       freopen("input.txt", "r", stdin);
       freopen("output.txt", "w", stdout);
    #endif
      IOS
     int t = 1;
     //cin >> t;
     while(t--){
        solve();
     }
    return 0;
}

1
BeruboIV 26 październik 2020, 14:45

1 odpowiedź

Najlepsza odpowiedź

{X0}} użyje możliwości zestawu do wyszukiwania < EM> Wartość efektywnie (logarytmiczny w odniesieniu do rozmiaru pojemnika).

Dla std::upper_bound, używając non - LegacyRandomAccessIterators, Podobnie jak iteratorzy std::set ({x3}} s), liczba przyrostów iteratora jest liniowa.

4
Ted Lyngmo 26 październik 2020, 11:56