whoisharsh's blog

By whoisharsh, history, 9 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

Full text and comments »

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