Условие

Условието на английски в acm.timus.ru

Времево ограничение: 2.0 секунди

Ограничение по памет: 16 MB

Сегмент на числовата ос от 0 до 10⁹ е оцветен в бяло. След това части от него са оцветени в черно, след това части в бяло и т.н. Общо са извършени N преоцветявания (1 ≤ N ≤ 5000).

Трябва да се напише програма, която намира най-големия непрекъснат бял интервал след всички оцветявания.

Вход

Първият ред от входа съдържа само числото N. Следващите N реда съдържат информация за оцветяванията. Всеки ред изглежда по следния начин:

a_i b_i c_i

където a_i and b_i са цели числа, c_i е символа 'b' или 'w'; a_i, b_i, c_i са разделени с интервал. Трите части се използват, за да се означи оцветяване на сегмент от a_i до b_i с цвят c_i ('w' — бяло, 'b' — черно). Приемете, че 0 < a_i < b_i < 10⁹.

Изход

Изходът се състои от две числа x и y (x < y), разделени с интервал. Тези числа трябва да определят най-дългия непрекъснат бял сегмент. Ако има повече от един такъв сегмент, изходът трябва да съдържа този с най-малък x.

Решение

Поради дадените ограничения в условието е невъзможно да използваме директен подход, т.е. да имаме един масив от 10⁹ елемента, в който да отбелязваме и следим цвета на всяко число от числовата ос. Подобна реализация би заела прекалено много памет и обхождането на масива би било много бавно.

Оптимизация на този подход обаче може да се направи много лесно, след като забележим следната особеност на крайния резултат: след последното боядисване получилата се числова ос ще бъде разделена на черно-бели сегменти с дължина по-голяма или равна на едно и краищата на тези сегменти винаги ще съвпадат с някой край на боядисване, т.е. с някое a_i или b_i. Важно е да се отбележи, че накрая не всяко a_i или b_i е на граница между бял и черен сегмент (в кода на C++ използвам turning point - точка на обръщане), но всички граници съвпадат с някое a_i или b_i.

След като сме забелязали тази особеност лесно се вижда оптимизацията, която можем да използваме: вместо да следим промените на цвета из цялата числова ос, ние се интересуваме само от сегментите, определени от краищата на оцветяванията a_i, b_i, 0 и 10⁹, максималният брой на които е ≤ N + 2 ≤ 10002. Това вече е много по-приемлив обем на данни, с които можем да работим.

Алгоритъмът за решаването на задачата се състои следното:

• При четенето на данните събираме всички a_i и b_i в един масив.
• Сортираме този масив, за да можем след това:
  • да търсим бързо в него с двоично търсене
  • при дадено оцветяване на оста от точка A до точка B да можем бързо да оцветим всички междинни точки.
• За всяко едно поредно оцветяване намираме позициите в сортирания мавис краищата на оцветяването и "оцветяваме" всички сегменти между тях и тях включително в новия цвят.
• Обхождаме масива с цветовете на сегментите и намираме най-дългия бял сегмент в него

Код на C++

#include <iostream>
#include <algorithm>

using namespace std;

int n;

int left_end[5010], right_end[5010]; // левите и десните краища на всички пребоядисани участъци
char color[5010]; // цвета на всички пребоядисани участъци

int tpoint_c = 2; // брояч
int tpoints[10020]; // (turning points) тук запазваме сортирани точките от числовата ос, в които е възможно да има два различни съседни цвята

bool segment[10020]; // масив, представляващ частите на които е разделена числовата ос от точките в tpoints, и съдържащ цвета на съответния сегмент (true = white, false = black)

// Функция за двоично търсене в масива tpoints
int binsearch (int val)
{
    int l = 1, r = tpoint_c, mid;
    // По построение ни е гарантирано, че търсената стойност съществува
    while (true)
    {
        mid = (l + r)/2;
        if (tpoints[mid] == val)
        {
            return mid;
        }
        else if (tpoints[mid] > val)
        {
            r = mid - 1;
        }
        else if (tpoints[mid] < val)
        {
            l = mid + 1;
        }
    }
}

int main()
{
    // Инициализираме променливите
    memset(tpoints, 0, sizeof(tpoints));
    for(int i = 0; i <= 5001; i++) segment[i] = true;
    
    cin >> n;
    
    // Третираме първоначалното състояние просто като първото пребоядисване
    tpoints[1] = left_end[1]  = 0;
    tpoints[2] = right_end[1] = 1000000000;
    color[1] = 'w';
    n++;
    
    // Прочитаме входа и попълваме tpoints масива с крайните точки на пребоядисванията
    for(int i = 2; i <= n ; i++)
    {
        cin >> left_end[i] >> right_end[i] >> color[i];
        tpoints[++tpoint_c] = left_end[i];
        tpoints[++tpoint_c] = right_end[i];
    }
   
    // сортираме масива, за да може по-късно да ползваме двоично търсене в него
    sort((tpoints+1), (tpoints + tpoint_c + 1));
    

    // За всеки интервал на пребоядисване взимаме лявата и дясна част, намираме къде са те спрямо другите краища в сортирания масив tpoints
    // и след това оцветяваме съответния сегмент от числовата ос в този цвят
    for(int i = 1; i <= n; i++)
    {
        int ll = binsearch(left_end[i]) + 1, rr = binsearch(right_end[i]);
        for (int j = ll; j <= rr; j++)
        {
            segment[j] = (color[i] == 'w');
        }
    }

    // След като всичко сме оцветили остава да намерим най-дългия бял сегмент от числовата ос
    int end, len = 0, maxlen = 0;
    for(int i = 2; i <= tpoint_c; i++)
    {
        if (segment[i])
        {
            len += tpoints[i] - tpoints[i - 1];   
        }
        else
        {
            if (len > maxlen)
            {
                maxlen = len;
                end = tpoints[i - 1];
            }
            len = 0;   
        }
    }
    
    if (len > maxlen)
    {
        maxlen = len;
        end = tpoints[tpoint_c];
    }
    
    cout << (end - maxlen) << " " << end << endl;
}