Блог пользователя Uncle

Автор Uncle, история, 3 года назад, По-английски

QUESTION IMAGE this is my code it's giving TLE i dunno why


/*------Jai Mata Di------*/ #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define dbg(x) cout << #x << " = " << x << "\n"; #define all(x) (x).begin(), (x).end() #define ff first #define ss second #define srt(s) sort(all(s)) #define S size() #define f(i, m, n) for (ll i = m; i < n; i++) void solve() { ll A, B; cin >> A >> B; map<ll, ll> m;map <ll,ll>n; f(i, 0, A) { ll k; cin >> k; m[i+1]=k;n[k]=i+1; } ll ans=1;f(i,1,n.S)if(n[i]>n[i+1])ans++; f(i, 0, B) { ll x, y; cin >> x >> y; ll a=m[x],b=m[y]; if(a>1 and n[a]<n[a-1])ans--; if(a<A and n[a+1]<n[a])ans--; if(b>1)if(b-1!=a)if(n[b]<n[b-1])ans--; if(b<A)if(b+1!=a)if(n[b+1]<n[b])ans--; swap(m[x],m[y]);swap(n[a],n[b]); if(a>1)if(n[a]<n[a-1])ans++; if(a<A)if(n[a+1]<n[a])ans++; if(b>1)if(b-1!=a)if(n[b]<n[b-1])ans++; if(b<A)if(b+1!=a)if(n[b+1]<n[b])ans++; cout<<ans<<endl; } } int main() { ios::sync_with_stdio(0); cin.tie(0); ll t = 1; while (t--) solve(); return 0; }

and here's the code that works (despite it looks similar )

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     int n, k, a, b, pass = 0;
     cin >> n >> k;
     vector<int> numbers(n + 1);
     vector<int> location(n + 1);
     map<int, int> numpairs;
     for (int i = 1; i <= n; i++)
     {
          cin >> numbers[i];
          location[numbers[i]] = i;
     }

     for (int i = 1; i < n; i++)
          if (location[i + 1] < location[i])
               pass++;
     pass++;

     while (k--)
     {
          cin >> a >> b;

          // put the numbers but we will check for boundary cond

          if (numbers[a] - 1 >= 1)
               numpairs.insert({numbers[a] - 1, numbers[a]});
          if (numbers[a] + 1 <= n)
               numpairs.insert({numbers[a], numbers[a] + 1});
          if (numbers[b] - 1 >= 1)
               numpairs.insert({numbers[b] - 1, numbers[b]});
          if (numbers[b] + 1 <= n)
               numpairs.insert({numbers[b], numbers[b] + 1});

          for (auto it = numpairs.begin(); it != numpairs.end(); it++)
               if (location[it->first] > location[it->second])
                    pass--;

          swap(numbers[a], numbers[b]);
          location[numbers[a]] = a;
          location[numbers[b]] = b;

          for (auto it = numpairs.begin(); it != numpairs.end(); it++)
               if (location[it->first] > location[it->second])
                    pass++;

          cout << pass << "\n";
          numpairs.clear();
     }
}

it will be helpful if anyone can assist

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
3 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

hint : answer is equal to number of inversions considering pairwise consecutive numbers

»
3 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +16 Проголосовать: не нравится

Use an array instead of std::map:
AC in 0.32/0.36 s
diff

Use '\n' instead of std::endl:
AC in 0.06/0.10 s
diff

  • »
    »
    3 года назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    it worked, can you share the reason

    • »
      »
      »
      3 года назад, скрыть # ^ |
      ← Rev. 3  
      Проголосовать: нравится +4 Проголосовать: не нравится

      Operations on map are $$$O(\log (\text{size of map}))$$$ and quite slow in practice, while operations on array are $$$O(1)$$$ and very fast in practice.

      endl flushes the output buffer, i.e. it immediately prints the current stuff to the output. This is quite slow.

      Just using '\n' doesn't flush the output, i.e. the output gets stored in separate memory. Only when execution ends is this output flushed. Only flushing once is much faster than flushing $$$n$$$ times.