Skip to content
Programming101
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programmingoneonone

HackerEarth Monk and Otakuland problem solution

YASH PAL, 31 July 2024
In this HackerEarth Monk and Otakuland problem Monk lives in Otakuland. Otakuland consists of N vertices and N-1 directed edges. i-th edge is a directed edge either from i-th vertex to i+1-th vertex or from i+1-th vertex to i-th vertex. You are given M Queries. Queries are 2 types:
  1. r – Reverse the direction of the edges between l-th vertex and r-th vertex.
  2. f t – Output the minimum number of edges which you have to reverse the direction to arrive from f to t.
HackerEarth Monk and Otakuland problem solution

HackerEarth Monk and Otakuland problem solution.

using System;
using System.Linq;
using System.Diagnostics;
using System.Collections.Generic;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
using System.Numerics;

namespace Program
{

public class Solver
{
public void Solve()
{
var n = sc.Integer();
var m = sc.Integer();
var s = sc.Scan();
var seg = new LazyEvaluateDirectionTree(n - 1);
for (int i = 0; i < n - 1; i++)
{
if (s[i] == '<')
seg.Reverse(i, i + 1);
}
for (int i = 0; i < m; i++)
{
var t = sc.Integer();
var l = sc.Integer() - 1;
var r = sc.Integer() - 1;
if (t == 1)
{
seg.Reverse(l, r);
}
else
{
var rev = false;
if (l > r) { rev = true; Swap(ref l, ref r); }
var ret = seg.Query(l, r);
var ans = rev ? ret.x : ret.y;
IO.Printer.Out.WriteLine(ans);
}
}
}
public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput());
static T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
}

}

#region main
static class Ex
{
static public string AsString(this IEnumerable<char> ie) { return new string(System.Linq.Enumerable.ToArray(ie)); }
static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") { return string.Join(st, ie); }
static public void Main()
{
var solver = new Program.Solver();
solver.Solve();
Program.IO.Printer.Out.Flush();
}
}
#endregion
#region Ex
namespace Program.IO
{
using System.IO;
using System.Text;
using System.Globalization;
public class Printer : StreamWriter
{
static Printer() { Out = new Printer(Console.OpenStandardOutput()) { AutoFlush = false }; }
public static Printer Out { get; set; }
public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
public Printer(System.IO.Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
public Printer(System.IO.Stream stream, Encoding encoding) : base(stream, encoding) { }
public void Write<T>(string format, T[] source) { base.Write(format, source.OfType<object>().ToArray()); }
public void WriteLine<T>(string format, T[] source) { base.WriteLine(format, source.OfType<object>().ToArray()); }
}
public class StreamScanner
{
public StreamScanner(Stream stream) { str = stream; }
public readonly Stream str;
private readonly byte[] buf = new byte[1024];
private int len, ptr;
public bool isEof = false;
public bool IsEndOfStream { get { return isEof; } }
private byte read()
{
if (isEof) return 0;
if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 1024)) <= 0) { isEof = true; return 0; } }
return buf[ptr++];
}
public char Char() { byte b = 0; do b = read(); while ((b < 33 || 126 < b) && !isEof); return (char)b; }

public string Scan()
{
var sb = new StringBuilder();
for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
sb.Append(b);
return sb.ToString();
}
public string ScanLine()
{
var sb = new StringBuilder();
for (var b = Char(); b != 'n'; b = (char)read())
if (b == 0) break;
else if (b != 'r') sb.Append(b);
return sb.ToString();
}
public long Long()
{
if (isEof) return long.MinValue;
long ret = 0; byte b = 0; var ng = false;
do b = read();
while (b != 0 && b != '-' && (b < '0' || '9' < b));
if (b == 0) return long.MinValue;
if (b == '-') { ng = true; b = read(); }
for (; true; b = read())
{
if (b < '0' || '9' < b)
return ng ? -ret : ret;
else ret = ret * 10 + b - '0';
}
}
public int Integer() { return (isEof) ? int.MinValue : (int)Long(); }
public double Double() { var s = Scan(); return s != "" ? double.Parse(Scan(), CultureInfo.InvariantCulture) : double.NaN; }
private T[] enumerate<T>(int n, Func<T> f)
{
var a = new T[n];
for (int i = 0; i < n; ++i) a[i] = f();
return a;
}

public char[] Char(int n) { return enumerate(n, Char); }
public string[] Scan(int n) { return enumerate(n, Scan); }
public double[] Double(int n) { return enumerate(n, Double); }
public int[] Integer(int n) { return enumerate(n, Integer); }
public long[] Long(int n) { return enumerate(n, Long); }
}
}
#endregion

#region LazyEvalDirection
public class LazyEvaluateDirectionTree
{
static readonly Pair<int, int> ZERO = Pair.Create(0, 0);
int n;
Pair<int, int>[] data;
bool[] rev;
public LazyEvaluateDirectionTree(int size)
{
n = 1;
while (n < size)
n <<= 1;
data = new Pair<int, int>[n << 1];
rev = new bool[n << 1];
for (int i = 0; i < size; i++)
data[i + n] = Pair.Create(1, 0);
for (int i = n - 1; i >0; i--)
{
eval(i);
}

}
private void lazyEval(int k, int a, int b)
{
if (!rev[k])
return;
Reverse(a, (a + b) >> 1, k << 1, a, (a + b) >> 1);
Reverse((a + b) >> 1, b, (k << 1) + 1, (a + b) >> 1, b);
rev[k] = false;
}
private void eval(int k)
{
int l = k << 1, r = (k << 1) + 1;
data[k] = Pair.Create(data[l].x + data[r].x, data[l].y + data[r].y);
}
public void Reverse(int a, int b)
{
Reverse(a, b, 1, 0, n);
}
private void Reverse(int a, int b, int k, int l, int r)
{
if (r <= a || b <= l)
return;
else if (a <= l && r <= b)
{
rev[k] = !rev[k];
Swap(ref data[k].x, ref data[k].y);
}
else
{
lazyEval(k, l, r);
Reverse(a, b, k << 1, l, (l + r) >> 1);
Reverse(a, b, (k << 1) + 1, (l + r) >> 1, r);
eval(k);
}
}
public Pair<int, int> Query(int a, int b) { return Query(a, b, 1, 0, n); }
private Pair<int, int> Query(int a, int b, int k, int l, int r)
{
if (r <= a || b <= l)
return ZERO;
if (a <= l && r <= b)
return data[k];
else
{
lazyEval(k, l, r);
var vl = Query(a, b, k << 1, l, (l + r) >> 1);
var vr = Query(a, b, (k << 1) + 1, (l + r) >> 1, r);
eval(k);
return Pair.Create(vl.x + vr.x, vl.y + vr.y);
}
}
static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }

}
#endregion

#region Compair
static public class Pair
{
static public Pair<FT, ST> Create<FT, ST>(FT f, ST s)
where FT : IComparable<FT>
where ST : IComparable<ST>
{ return new Pair<FT, ST>(f, s); }
static public Pair<FT, ST> Min<FT, ST>(Pair<FT, ST> p, Pair<FT, ST> q)
where FT : IComparable<FT>
where ST : IComparable<ST>
{ return (p.CompareTo(q) <= 0) ? p : q; }
static public Pair<FT, ST> Max<FT, ST>(Pair<FT, ST> p, Pair<FT, ST> q)
where FT : IComparable<FT>
where ST : IComparable<ST>
{ return (p.CompareTo(q) >= 0) ? p : q; }
}
public struct Pair<FT, ST> : IComparable<Pair<FT, ST>>
where FT : IComparable<FT>
where ST : IComparable<ST>
{
public FT x;
public ST y;
public Pair(FT f, ST s) : this() { x = f; y = s; }

public int CompareTo(Pair<FT, ST> other)
{
var cmp = x.CompareTo(other.x);
return cmp != 0 ? cmp : y.CompareTo(other.y);
}
public override string ToString() { return string.Format("{0} {1}", x, y); }
}

Second solution

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cctype>
#include<cstdlib>
#include<algorithm>
#include<bitset>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<complex>
#include<functional>
#include<climits>
#include<cassert>
#include<iterator>
#include<unordered_map>
#include<unordered_set>
//#include<quadmath.h>
using namespace std;

namespace test{
void end_test(){
int val;
if (cin >> val){
exit(1);
}
}
void range_test(int t, int l, int r){
if (t < l || r < t){
exit(1);
}
}
}
struct st{
int countt;
int countt1;
int rev;
st(){
countt = countt1 = 0;
rev = 0;
}
};
#define MAX 200000
st seg[MAX * 4];
void update(int b){
seg[b].rev %= 2;
if (seg[b].rev){
swap(seg[b].countt, seg[b].countt1);
}
if (b * 2 + 2 < MAX * 4){
seg[b * 2 + 1].rev += seg[b].rev;
seg[b * 2 + 2].rev += seg[b].rev;
}
seg[b].rev = 0;
}
st merge(st a, st b){
st r;
r.countt = a.countt + b.countt;
r.countt1 = a.countt1 + b.countt1;
return r;
}
st emp;
inline st q(int b, int l, int r, int ll, int rr){
update(b);
if (ll <= l&&r <= rr){
return seg[b];
}
if (r <= ll || rr <= l){
return emp;
}
return merge(q(b * 2 + 1, l, (l + r) >> 1, ll, rr), q(b * 2 + 2, (l + r) >> 1, r, ll, rr));
}
inline void add(int b, int l, int r, int ll, int rr){
update(b);
if (ll <= l&&r <= rr){
seg[b].rev++;
update(b);
return;
}
if (rr <= l || r <= ll){
return;
}
add(b * 2 + 1, l, (l + r) >> 1, ll, rr);
add(b * 2 + 2, (l + r) >> 1, r, ll, rr);
seg[b] = merge(seg[b * 2 + 1], seg[b * 2 + 2]);
}
char a[MAX];
inline void init(int b, int l, int r){
if (l + 1 == r){
if (a[l] == '<'){
seg[b].countt++;
}
else{
seg[b].countt1++;
}
return;
}
init(b * 2 + 1, l, (l + r) >> 1);
init(b * 2 + 2, (l + r) >> 1, r);
seg[b] = merge(seg[b * 2 + 1], seg[b * 2 + 2]);
}
int main(){
int n;
int m;
scanf("%d%d", &n, &m);
test::range_test(n, 2, 200000);
test::range_test(m, 1, 200000);
scanf("%s", a);
init(0, 0, n - 1);
long long int T=0;
while (m--){
int ty;
scanf("%d", &ty);
test::range_test(ty, 1, 2);
if (ty == 1){
int l, r;
scanf("%d%d", &l, &r);
test::range_test(l, 1, n);
test::range_test(r, 1, n);
l--;
r--;
add(0, 0, n - 1, l, r);
continue;
}
int f, t;
scanf("%d%d", &f, &t);
T+=(long long int)(abs(f-t));
test::range_test(1, 1, n);
test::range_test(1, 1, n);
f--;
t--;
if (f == t){
puts("0");
continue;
}
int l = min(f, t);
int r = max(f, t);
st ans = q(0, 0, n - 1, l, r);
if (f > t){
printf("%dn", ans.countt1);
}
else{
printf("%dn", ans.countt);
}
}
test::end_test();
/*if(T<100000000){
exit(1); //brute-force solution
}*/
return 0;
}
coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes