SHARE
TWEET

Untitled

a guest May 16th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.IO;
  3.  
  4. namespace Fence
  5. {
  6.     class Program
  7.     {
  8.         static void Main(string[] args)
  9.         {
  10.             using (StreamReader sr = new StreamReader("fence.in"))
  11.             using (StreamWriter sw = new StreamWriter("fence.out"))
  12.             {
  13.                 String[] input = new String[3];
  14.                 int start = 1048576;
  15.                 SegmentTree tree = new SegmentTree();
  16.                 Element result = new Element();
  17.                 int from, to;
  18.                 while (!sr.EndOfStream)
  19.                 {
  20.                     input = sr.ReadLine().Split();
  21.                     if (input[0][0] == 'L')
  22.                     {
  23.                         from = Convert.ToInt32(input[1]);
  24.                         to = Convert.ToInt32(input[2]);
  25.                         tree.Modify(0, 1, start, from, to);
  26.                     }
  27.                     else
  28.                     {
  29.                         if (input[0][0] == 'W')
  30.                         {
  31.                             from = Convert.ToInt32(input[1]);
  32.                             to = Convert.ToInt32(input[2]);
  33.                             result = tree.Query(0, 1, start, from, to);
  34.                             sw.WriteLine(result.maxNotColored + " " + result.maxColored);
  35.                         }
  36.                     }
  37.                 }
  38.             }
  39.         }
  40.     }
  41. }
  42.  
  43. class SegmentTree
  44. {
  45.     public int[] maxColored;
  46.     public int[] maxNotColored;
  47.     public bool[] leftColored;
  48.     public bool[] rightColored;
  49.     public int[] leftNumColoredOrNotColored;
  50.     public int[] rightNumColoredOrNotColored;
  51.     public bool[] isAddColor;
  52.  
  53.     public SegmentTree()
  54.     {
  55.         maxColored = new int[2097152];
  56.         maxNotColored = new int[2097152];
  57.         leftNumColoredOrNotColored = new int[2097152];
  58.         rightNumColoredOrNotColored = new int[2097152];
  59.         leftColored = new bool[2097152];
  60.         rightColored = new bool[2097152];
  61.         isAddColor = new bool[2097152];
  62.     }
  63.  
  64.     public void Modify(int pos, int left, int right, int queryLeft, int queryRight)
  65.     {
  66.         if (!isAddColor[pos])
  67.         {
  68.             if(maxColored[pos] == 0)
  69.             {
  70.                 maxNotColored[pos] = right - left + 1;
  71.                 leftColored[pos] = false;
  72.                 rightColored[pos] = false;
  73.                 rightNumColoredOrNotColored[pos] = right - left + 1;
  74.                 leftNumColoredOrNotColored[pos] = right - left + 1;
  75.             }
  76.             if (left > queryRight || right < queryLeft)
  77.             {
  78.                 return;
  79.             }
  80.             if (queryLeft <= left && right <= queryRight)
  81.             {
  82.                 isAddColor[pos] = true;
  83.                 maxColored[pos] = leftNumColoredOrNotColored[pos] = rightNumColoredOrNotColored[pos] = right - left + 1;
  84.                 leftColored[pos] = true;
  85.                 rightColored[pos] = true;
  86.                 maxNotColored[pos] = 0;
  87.                 return;
  88.             }
  89.             int mid = (left + right) / 2;
  90.             Modify(pos * 2 + 1, left, mid, queryLeft, queryRight);
  91.             Modify(pos * 2 + 2, mid + 1, right, queryLeft, queryRight);
  92.             FunctionOfTree(pos * 2 + 1, left, mid, pos * 2 + 2, mid + 1, right, pos);
  93.         }
  94.     }
  95.  
  96.     public Element FunctionOfTree(Element a, int leftA, int rightA, Element b, int leftB, int rightB)
  97.     {
  98.         Element result = new Element();
  99.         if (a.maxColored == -1)
  100.         {
  101.             return b;
  102.         }
  103.         if (b.maxColored == -1)
  104.         {
  105.             return a;
  106.         }
  107.         int tmp;
  108.         result.maxColored = Math.Max(a.maxColored, b.maxColored);
  109.         result.maxNotColored = Math.Max(a.maxNotColored, b.maxNotColored);
  110.         result.leftNumColoredOrNotColored = a.leftNumColoredOrNotColored;
  111.         result.rightNumColoredOrNotColored = b.rightNumColoredOrNotColored;
  112.         if (a.rightColored == b.leftColored)
  113.         {
  114.             tmp = a.rightNumColoredOrNotColored + b.leftNumColoredOrNotColored;
  115.             if (a.rightColored)
  116.             {
  117.                 if (tmp > result.maxColored)
  118.                 {
  119.                     result.maxColored = tmp;
  120.                     if (rightA - a.rightNumColoredOrNotColored + 1 == leftA)
  121.                     {
  122.                         result.leftNumColoredOrNotColored = result.maxColored;
  123.                     }
  124.                     if (leftB + b.leftNumColoredOrNotColored - 1 == rightB)
  125.                     {
  126.                         result.rightNumColoredOrNotColored = result.maxColored;
  127.                     }
  128.                 }
  129.             }
  130.             else
  131.             {
  132.                 if (tmp > result.maxNotColored)
  133.                 {
  134.                     result.maxNotColored = tmp;
  135.                     if (rightA - a.rightNumColoredOrNotColored + 1 == leftA)
  136.                     {
  137.                         result.leftNumColoredOrNotColored = result.maxNotColored;
  138.                     }
  139.                     if (leftB + b.leftNumColoredOrNotColored - 1 == rightB)
  140.                     {
  141.                         result.rightNumColoredOrNotColored = result.maxNotColored;
  142.                     }
  143.                 }
  144.             }
  145.         }
  146.         result.leftColored = a.leftColored;
  147.         result.rightColored = b.rightColored;
  148.         result.isAddColor = a.isAddColor && b.isAddColor;
  149.         return result;
  150.     }
  151.  
  152.     public Element FunctionOfTree(int posLeft, int leftA, int rightA, int posRight, int leftB, int rightB, int pos)
  153.     {
  154.         Element result = new Element();
  155.         if (maxColored[posLeft] == -1)
  156.         {
  157.             result = new Element
  158.             {
  159.                 maxColored = maxColored[posRight],
  160.                 maxNotColored = maxNotColored[posRight],
  161.                 leftNumColoredOrNotColored = leftNumColoredOrNotColored[posRight],
  162.                 rightNumColoredOrNotColored = rightNumColoredOrNotColored[posRight],
  163.                 isAddColor = isAddColor[posRight],
  164.                 leftColored = leftColored[posRight],
  165.                 rightColored = rightColored[posRight]
  166.             };
  167.             return result;
  168.         }
  169.         if (maxColored[posRight] == -1)
  170.         {
  171.             result = new Element
  172.             {
  173.                 maxColored = maxColored[posLeft],
  174.                 maxNotColored = maxNotColored[posLeft],
  175.                 leftNumColoredOrNotColored = leftNumColoredOrNotColored[posLeft],
  176.                 rightNumColoredOrNotColored = rightNumColoredOrNotColored[posLeft],
  177.                 isAddColor = isAddColor[posLeft],
  178.                 leftColored = leftColored[posLeft],
  179.                 rightColored = rightColored[posLeft]
  180.             };
  181.             return result;
  182.         }
  183.         int tmp;
  184.         result.maxColored = Math.Max(maxColored[posLeft], maxColored[posRight]);
  185.         result.maxNotColored = Math.Max(maxNotColored[posLeft], maxNotColored[posRight]);
  186.         result.leftNumColoredOrNotColored = leftNumColoredOrNotColored[posLeft];
  187.         result.rightNumColoredOrNotColored = rightNumColoredOrNotColored[posRight];
  188.         if (rightColored[posLeft] == leftColored[posRight])
  189.         {
  190.             tmp = rightNumColoredOrNotColored[posLeft] + leftNumColoredOrNotColored[posRight];
  191.             if (rightColored[posLeft])
  192.             {
  193.                 if (tmp > result.maxColored)
  194.                 {
  195.                     result.maxColored = tmp;
  196.                     if (rightA - rightNumColoredOrNotColored[posLeft] + 1 == leftA)
  197.                     {
  198.                         result.leftNumColoredOrNotColored = result.maxColored;
  199.                     }
  200.                     if (leftB + leftNumColoredOrNotColored[posRight] - 1 == rightB)
  201.                     {
  202.                         result.rightNumColoredOrNotColored = result.maxColored;
  203.                     }
  204.                 }
  205.             }
  206.             else
  207.             {
  208.                 if (tmp > result.maxNotColored)
  209.                 {
  210.                     result.maxNotColored = tmp;
  211.                     if (rightA - rightNumColoredOrNotColored[posLeft] + 1 == leftA)
  212.                     {
  213.                         result.leftNumColoredOrNotColored = result.maxNotColored;
  214.                     }
  215.                     if (leftB + leftNumColoredOrNotColored[posRight] - 1 == rightB)
  216.                     {
  217.                         result.rightNumColoredOrNotColored = result.maxNotColored;
  218.                     }
  219.                 }
  220.             }
  221.         }
  222.         result.leftColored = leftColored[posLeft];
  223.         result.rightColored = rightColored[posRight];
  224.         result.isAddColor = isAddColor[posLeft] && isAddColor[posRight];
  225.         maxColored[pos] = result.maxColored;
  226.         maxNotColored[pos] = result.maxNotColored;
  227.         leftNumColoredOrNotColored[pos] = result.leftNumColoredOrNotColored;
  228.         rightNumColoredOrNotColored[pos] = result.rightNumColoredOrNotColored;
  229.         isAddColor[pos] = result.isAddColor;
  230.         leftColored[pos] = result.leftColored;
  231.         rightColored[pos] = result.rightColored;
  232.         return result;
  233.     }
  234.  
  235.     public Element Query(int pos, int left, int right, int queryLeft, int queryRight)
  236.     {
  237.         if (left > queryRight || right < queryLeft)
  238.         {
  239.             Element result = new Element
  240.             {
  241.                 maxColored = -1
  242.             };
  243.             return result;
  244.         }
  245.         if (queryLeft <= left && right <= queryRight)
  246.         {
  247.             Element result = new Element
  248.             {
  249.                 maxColored = maxColored[pos],
  250.                 maxNotColored = maxNotColored[pos],
  251.                 leftNumColoredOrNotColored = leftNumColoredOrNotColored[pos],
  252.                 rightNumColoredOrNotColored = rightNumColoredOrNotColored[pos],
  253.                 isAddColor = isAddColor[pos],
  254.                 leftColored = leftColored[pos],
  255.                 rightColored = rightColored[pos]
  256.             };
  257.             return result;
  258.         }
  259.         if (maxColored[pos] == 0)
  260.         {
  261.             if (left <= queryLeft && right >= queryRight)
  262.             {
  263.                 return new Element(queryLeft, queryRight);
  264.             }
  265.             else
  266.             {
  267.                 if (left <= queryLeft) {
  268.                     return new Element(queryLeft, right);
  269.                 }
  270.                 else
  271.                 {
  272.                     if(right >= queryRight)
  273.                     {
  274.                         return new Element(left, queryRight);
  275.                     }
  276.                 }
  277.             }
  278.         }
  279.         if (isAddColor[pos])
  280.         {
  281.             if (left <= queryLeft && right >= queryRight)
  282.             {
  283.                 return new Element(queryRight - queryLeft + 1);
  284.             }
  285.             else
  286.             {
  287.                 if (left <= queryLeft)
  288.                 {
  289.                     return new Element(right - queryLeft + 1);
  290.                 }
  291.                 else
  292.                 {
  293.                     if (right >= queryRight)
  294.                     {
  295.                         return new Element(queryRight - left + 1);
  296.                     }
  297.                 }
  298.             }
  299.         }
  300.         int mid = (left + right) / 2;
  301.         if (mid >= queryRight && left <= queryLeft)
  302.         {
  303.             return Query(pos * 2 + 1, left, mid, queryLeft, queryRight);
  304.         }
  305.         if (mid + 1 <= queryLeft && right >= queryRight)
  306.         {
  307.             return Query(pos * 2 + 2, mid + 1, right, queryLeft, queryRight);
  308.         }
  309.         return FunctionOfTree(Query(pos * 2 + 1, left, mid, queryLeft, queryRight), left, mid,
  310.             Query(pos * 2 + 2, mid + 1, right, queryLeft, queryRight), mid + 1, right);
  311.     }
  312. }
  313.  
  314. class Element
  315. {
  316.     public int maxColored;
  317.     public int maxNotColored;
  318.     public bool leftColored;
  319.     public bool rightColored;
  320.     public int leftNumColoredOrNotColored;
  321.     public int rightNumColoredOrNotColored;
  322.     public bool isAddColor;
  323.  
  324.     public Element() {}
  325.     public Element(int left, int right)
  326.     {
  327.         maxNotColored = right - left + 1;
  328.         leftNumColoredOrNotColored = rightNumColoredOrNotColored = maxNotColored;
  329.         leftColored = false;
  330.         rightColored = false;
  331.         isAddColor = false;
  332.     }
  333.  
  334.     public Element(int maxColored)
  335.     {
  336.         this.maxColored = maxColored;
  337.         leftNumColoredOrNotColored = maxColored;
  338.         rightNumColoredOrNotColored = maxColored;
  339.         leftColored = true;
  340.         rightColored = true;
  341.         isAddColor = true;
  342.     }
  343. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top