HackerEarth Mancunian And Liverbird Go Bar Hopping problem solution

In this HackerEarth Mancunian And Liverbird Go Bar Hopping problem solution, It’s April Fools’ Day 2017 and to celebrate, Mancunian and his arch-enemy Liverbird decide to put aside their differences and go have a drink together.

There are N bars (numbered from 1 to N) located in a straight line. The ith is located at point i on the line. Apart from this, there are N-1 roads, the ith of which connects the ith and i+1th bars. Note that the roads are unidirectional. You are given the initial orientation of each road.

On celebratory occasions such as these, there are a lot of people on the streets. Hence, the police have to take special measures to combat traffic congestion. Periodically, they issue a directive to reverse the direction of all the roads. What this means is that, if there was a road directed from bar numbered i to bar i+1, after the update, it will be directed from i+1 to i.

You are given a set of operations. Each operation can be either an update or a query. Update is the one described above. In each query, you are given the location of the bar the two partyers are located at currently. You have to count the number of bars (including the current location) that are reachable from their current location.

HackerEarth Mancunian And Liverbird Go Bar Hopping problem solution.

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define MOD (1000000007LL)

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

ll pwr(ll base, ll p, ll mod = MOD){
ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
}


#define LEFT 0
#define RIGHT 1
const int N = 1000*1000+2;
int n, arr[N], cnt[N][2][2];


int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    assert(n >= 1 && n <= 1000*1000);
    for(int i=1;i<=n-1;i++){
        cin>>arr[i];
        assert(arr[i] == 0 || arr[i] == 1);
    }

    for(int i=2;i<=n;i++){
        cnt[i][LEFT][arr[i-1]] = 1 + cnt[i-1][LEFT][arr[i-1]];
    }

    for(int i=n-1;i>=1;i--){
        cnt[i][RIGHT][arr[i]] = 1 + cnt[i+1][RIGHT][arr[i]];
    }

    int q;
    cin>>q;
    assert(q >= 1 && q <= 1000*1000);

    int state = 0;
    while(q--){

        char ch;
        cin>>ch;
        assert(ch == 'U' || ch == 'Q');

        if(ch == 'U'){
            
            state ^= 1;
        }
        else{
            
            int src;
            cin>>src;
            assert(src >= 1 && src <= n);

            int ans = 1 + cnt[src][LEFT][state^LEFT] + cnt[src][RIGHT][state^RIGHT];
            cout<<ans<<endl;
        }
    }

    return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;

#define MAXN 1000005
#define ii pair<int,int>
#define ff first
#define ss second
#define ll long long

int left_reach[MAXN][2];
int right_reach[MAXN][2];
int arr[MAXN];

int main(){
    int i,j,n,q,type,idx;
    string s;
    scanf("%d",&n);
    for(i=1;i<=n-1;i++)
        scanf("%d",&arr[i]);
    
    for(i=1;i<=n;i++)
        if(arr[i-1])    left_reach[i][1] = left_reach[i-1][1] + 1,left_reach[i][0] = 1;
        else            left_reach[i][0] = left_reach[i-1][0] + 1, left_reach[i][1] = 1;
        
    for(i=n;i>=1;i--)
        if(arr[i])      right_reach[i][0] = right_reach[i+1][0] + 1,right_reach[i][1] = 1;
        else            right_reach[i][1] = right_reach[i+1][1] + 1,right_reach[i][0] = 1;

    type = 0;
    scanf("%d",&q);
    while(q--){
        cin>>s;
        if(s[0]=='U')   type ^= 1;
        else            scanf("%d",&idx), printf("%dn",left_reach[idx][type]+right_reach[idx][type]-1);
    }
    


    return 0;
}

coding problems solutions