Advertisement
Guest User

Untitled

a guest
Jul 16th, 2019
287
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 3.54 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Collections;
  6.  
  7. namespace ConsoleApplication1
  8. {
  9.    
  10.  
  11.     class Program
  12.     {
  13.  
  14.         public class Interval
  15.         {
  16.             public int start;
  17.             public int end;
  18.             public Interval() { start = 0; end = 0; }
  19.             public Interval(int s, int e) { start = s; end = e; }
  20.         }
  21.  
  22.  
  23.         private static void quicksort(List<Interval> vector, int primero, int ultimo)
  24.         {
  25.             int  i, j, central;
  26.             int pivote;
  27.             central = (primero + ultimo) / 2;
  28.             pivote = vector[central].start;
  29.             i = primero;
  30.             j = ultimo;
  31.             do
  32.             {
  33.                 while (vector[i].start < pivote) i++;
  34.                 while (vector[j].start > pivote) j--;
  35.                 if (i <= j)
  36.                 {
  37.                     Interval temp;
  38.                     temp = vector[i];
  39.                     vector[i] = vector[j];
  40.                     vector[j] = temp;
  41.                     // vector.Set(i, vector.get(j));
  42.                     // vector.set(j, temp);
  43.  
  44.                     i++;
  45.                     j--;
  46.                 }
  47.             } while (i <= j);
  48.  
  49.             if (primero < j)
  50.             {
  51.                 quicksort(vector, primero, j);
  52.             }
  53.             if (i < ultimo)
  54.             {
  55.                 quicksort(vector, i, ultimo);
  56.             }
  57.         }
  58.  
  59.  
  60.  
  61.  
  62.         public static List<Interval> Merge(List<Interval> longervals)
  63.         {
  64.  
  65.             if (longervals == null || longervals.Count == 0) return longervals;
  66.  
  67.             quicksort(longervals, 0, longervals.Count - 1);
  68.  
  69.             int  i = 0;
  70.  
  71.             List<Interval> res = new List<Interval>();
  72.  
  73.             while (i < longervals.Count)
  74.             {
  75.                 Interval a = longervals[i];
  76.                 Interval insertar = a;
  77.                 while (i + 1 < longervals.Count && longervals[i + 1].start <= a.end)
  78.                 {
  79.  
  80.                     insertar = new Interval(Math.Min(a.start, longervals[i + 1].start), Math.Max(a.end, longervals[i + 1].end));
  81.                     a = insertar;
  82.                     i++;
  83.                 }
  84.                 res.Add(insertar);
  85.                 i++;
  86.             }
  87.  
  88.             return res;
  89.         }
  90.  
  91.  
  92.         static long sumarRango(long a, long b)
  93.         {
  94.  
  95.             return (b * (b + 1) / 2) - ((a - 1) * (a) / 2);
  96.         }
  97.  
  98.         static long sumarSobrantes(string[] longervalos)
  99.         {
  100.  
  101.             List<Interval> lista = new List<Interval>();
  102.             //cargo lista longervalos
  103.             for (long i = 0; i < longervalos.Length; i++)
  104.             {
  105.                 string[] item = longervalos[i].Split(' ');
  106.                 lista.Add(new Interval(int.Parse(item[0]), int.Parse(item[1])));
  107.             }
  108.  
  109.             lista = Merge(lista);
  110.  
  111.             long suma = 0;
  112.             foreach (Interval item in lista)
  113.             {
  114.                 suma += sumarRango(item.start, item.end);
  115.             }
  116.  
  117.             return sumarRango(1, 1000000) - suma;
  118.  
  119.         }
  120.  
  121.  
  122.         static void Main(string[] args)
  123.         {
  124.             long n = long.Parse(Console.ReadLine().Trim());
  125.  
  126.             string[] input = new string[n];
  127.             long i = 0;
  128.             while (n-- > 0)
  129.             {
  130.                 input[i++] = Console.ReadLine().Trim();
  131.             }
  132.  
  133.             Console.WriteLine(sumarSobrantes(input));
  134.  
  135.  
  136.             Console.ReadLine();
  137.         }
  138.  
  139.     }
  140. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement