HackerEarth Hard job problem solution YASH PAL, 31 July 2024 In this HackerEarth Hard job problem You are given a permutation of integers from 1 to N (very unusual :D). The only thing you should do is to process M queries. Each query has 2 parameters: number X from 1 to N and lowercase latin letter Y (either ‘l’ or ‘r’). You do the following: Calculate distances from the position of the number X to the left end and to the right end of the permutation. Let’s call minimum of them accessibleness. Erase number X from it’s current position. If parameter Y is ‘l’ then insert X the very beginning of the permutation. Otherwise insert X after the last element of the permutation. Please find sum of accessibleness over all queries. HackerEarth Hard job problem solution. #include <cstdio>#include <algorithm>#include <vector>#include <iostream>#include <set>#include <map>#include <iomanip>#include <string>#include <string.h>#include <cstdlib>#include <bitset>#include <cmath>#define X first#define Y second#define mp make_pair#define pb push_backtypedef long long ll;using namespace std;const int MAXN = 300100, MX = MAXN * 3;int r[MX];void modify(int x, int y) { for (; x < MX; x = (x|(x + 1))) { r[x] += y; }}int sum(int x) { int res = 0; for (; x >= 0; x = ((x&(x + 1) ) -1) ) { res += r[x]; } return res;}int lft = MAXN, rght, n, m;int wh[MAXN];int main() { scanf("%d%d", &n, &m); rght = lft + n - 1; for (int i = 0; i < n; i++) { modify(lft + i, 1); int x; scanf("%d", &x); wh[x] = lft + i; } long long ans = 0; for (int i = 0; i < m; i++) { int x; char go[5]; scanf("%d%s", &x, go); int A = sum(wh[x]); int B = sum(rght); ans += min(A - 1, B - A); modify(wh[x], -1); if (go[0] == 'l') { lft--; wh[x] = lft; modify(lft, 1); } else { rght++; wh[x] = rght; modify(rght, 1); } } cout<<ans<<endl; return 0;} Second solution #include<bits/stdc++.h>using namespace std;int t[1<<21];int n,m;int q,ps[1<<20],ptrl,ptrr;string st;long long ans;int sum(int r){ int res=0; for (;r>=0;r=(r&(r+1))-1) res+=t[r]; return res;}void add(int i, int val){ for (;i<=m*2+n+5;i=(i|(i+1))) t[i]+=val;}int sum(int l,int r){ return sum(r)-sum(l-1);}int main(){ios_base::sync_with_stdio(0);cin>>n>>m;for (int i=1;i<=n;i++){ cin>>q; ps[q]=i+m;}ptrl=m;ptrr=m+n+1;for (int i=1;i<=n;i++){ add(i+m,1);}int mm=m;for (;mm;--mm){ cin>>q; cin>>st; int res=min(sum(0,ps[q]),sum(ps[q],m*2+n+2)); ans+=res; if (st=="l") // end add(ptrl,1), add(ps[q],-1), ps[q]=ptrl, --ptrl; else add(ps[q],-1),// l add(ptrr,1), ps[q]=ptrr, ++ptrr;}cout<<ans<<endl;return 0;} coding problems