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


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_back

typedef 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;}