[toph.co] Reverse The Magic

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Reverse The Magic
Source            : toph.co
Category          : Data Structure
Algorithm         : Segment Tree, Lazy Propagation
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define pii                 pair <int, int>
 
static const int maxn = 1e5 + 5;
 
struct information
{
      int maxval, minval, lazy;
      information(int maxval = 0, int minval = 0, int lazy = -1) :
            maxval(maxval), minval(minval), lazy(lazy) {}
} Tree[maxn << 2];
 
inline void clean()
{
      for (int i = 0; i < (maxn << 2); i++) Tree[i] = information();
}
 
inline void ansUpate(pii &ans, pii child)
{
      if (child.first > ans.first) ans.first = child.first;
      if (child.second < ans.second) ans.second = child.second;
}
 
inline void updateLazy(int node, int val)
{
      Tree[node] = information(val, val, val);
}
 
inline void updateNode(int node)
{
      int lft = node << 1;
      int rgt = lft | 1;
      int val = Tree[node].lazy;
      Tree[lft] = Tree[rgt] = information(val, val, val);
      Tree[node].lazy = -1;
}
 
inline void update(int node, int a, int b, int i, int j, int par)
{
      if (a == i && b == j)
      {
            updateLazy(node, par);
            return;
      }
      if (Tree[node].lazy != -1)
      {
            updateNode(node);
      }
      int lft = node << 1;
      int rgt = lft | 1;
      int mid = (a + b) >> 1;
      if (j <= mid)
      {
            update(lft, a, mid, i, j, par);
      }
      else if (i > mid)
      {
            update(rgt, mid+1, b, i, j, par);
      }
      else
      {
            update(lft, a, mid, i, mid, par);
            update(rgt, mid+1, b, mid+1, j, par);
      }
      Tree[node].maxval = max(Tree[lft].maxval, Tree[rgt].maxval);
      Tree[node].minval = min(Tree[lft].minval, Tree[rgt].minval);
}
 
inline pii query(int node, int a, int b, int i, int j)
{
      if (a == i && b == j)
      {
            return pii(Tree[node].maxval, Tree[node].minval);
      }
      if (Tree[node].lazy != -1)
      {
            updateNode(node);
      }
      int lft = node << 1;
      int rgt = lft | 1;
      int mid = (a + b) >> 1;
      pii ans;
      ans.first = INT_MIN;
      ans.second = INT_MAX;
      if (j <= mid)
      {
            pii leftChild = query(lft, a, mid, i, j);
            ansUpate(ans, leftChild);
      }
      else if (i > mid)
      {
            pii rightChild = query(rgt, mid+1, b, i, j);
            ansUpate(ans, rightChild);
      }
      else
      {
            pii leftChild = query(lft, a, mid, i, mid);
            pii rightChild = query(rgt, mid+1, b, mid+1, j);
            ansUpate(ans, leftChild);
            ansUpate(ans, rightChild);
      }
      Tree[node].maxval = max(Tree[lft].maxval, Tree[rgt].maxval);
      Tree[node].minval = min(Tree[lft].minval, Tree[rgt].minval);
      return ans;
}
 
inline int read()
{
      int a;
      scanf("%d", &a);
      return a;
}
 
int queries[maxn];
 
int main()
{
      //freopen("in.txt", "r", stdin);
 
      int tc = read();
      for (int tcase = 1; tcase <= tc; tcase++)
      {
            clean();
            for (int i = 0; i < maxn; i++) queries[i] = -1;
 
            int N = read();
            int M = read();
            bool isTree = true;
            int maxL = -1;
            for (int i = 0; i < M; i++)
            {
                  int l = read();
                  int r = read();
                  ++l; ++r;
                  if (l > r) swap(l, r);
                  if (queries[l] != -1 && queries[l] != r) isTree = false;
                  queries[l] = r;
                  if (l == 1 && r != N) isTree = false;
                  if (l > maxL) maxL = l;
            }
            if (isTree == false)
            {
                  puts("No");
                  continue;
            }
            int ptr = 0;
            for (int i = 1; i <= maxL && isTree; i++)
            {
                  int l = i;
                  int r = queries[i];
                  if (r == -1) continue;
                  pii q = query(1, 1, N, l, r);
                  if (q.first != q.second) isTree = false;
                  update(1, 1, N, l, r, ++ptr);
            }
            puts(isTree ? "Yes" : "No");
      }
}