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

Автор whoisharsh, история, 9 месяцев назад, По-английски

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
  • Проголосовать: не нравится

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by whoisharsh (previous revision, new revision, compare).

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 месяцев назад, # |
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

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

    it worked, can you share the reason

    • »
      »
      »
      9 месяцев назад, # ^ |
      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.