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
hint : answer is equal to number of inversions considering pairwise consecutive numbers
Use an array instead of
std::map
:AC in 0.32/0.36 s
diff
Use
'\n'
instead ofstd::endl
:AC in 0.06/0.10 s
diff
it worked, can you share the reason
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.Here's my solution using a position array: https://cses.fi/paste/26b0b6f2b673e997b6ad12/