whoisharsh's blog

By whoisharsh, history, 8 months ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it worked, can you share the reason

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 3   Vote: I like it +4 Vote: I do not like it

      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.