HackerEarth Hard job problem solution

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

coding problems