SHARE
TWEET

Untitled

a guest Jun 27th, 2019 50 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. signed main() {
  6.     ios_base::sync_with_stdio(0);
  7.     cin.tie(0);
  8.     cout.tie(0);
  9.    
  10.     // сверху ничего особенного
  11.     int a;
  12.     cin>>a;
  13.     vector <pair<int,int>> seg(a);
  14.     for (int i=0;i<a;i++) cin>>seg[i].first>>seg[i].second;
  15.     // а - количество отрезков
  16.     // seg - вектор, в котором хранятся отрезки. seg[i].first - левая граница, seg[i].second - правая граница
  17.     sort(seg.begin(),seg.end());
  18.     //сортирую по левой границе, это делается встроенной сортировкой  
  19.     int mint[a+1];
  20.    
  21.     int max1[a];
  22.     // ща будет сложное определение
  23.     //Короче, max1[i] - максимальный размер набора который можно составить из первых i отрезков (в нулевой индексации)
  24.     // Очевидно, что max1 - монотонный массив, то есть max1[i-1]<=max1[i]
  25.     // Тогда, сделаем mint - массив, в котором хранится минимальное время,
  26.     // на котором заканчивается последняя тренировка в каком-либо наборе размера i
  27.     // задаю mint явно больше максимального значения
  28.     for (int i=1;i<=a;i++) {
  29.         mint[i]=1000000000000;
  30.     }
  31.     // первый отрезок очевидно как влияет на эти 2 массива, поэтому пересчитываю для первого отрезка - типа база индукции
  32.     mint[1]=seg[0].second;
  33.     max1[0]=1;
  34.    // for (int i=0;i<a;i++) cout<<seg[i].first<<" "<<seg[i].second<<"\n";
  35.    // цикл пересчёта этих массивов
  36.    // что в нём происходит - очевидно, что max1[i]-max1[i-1]<=1 (если не очевидно, подумай почему)
  37.    // Поэтому есть 2 варианта, которые разобраны в ифе.
  38.    // В этом цикле явно всё пересчитывается, если вдуматься то становится понятно
  39.     for (int i=1;i<a;i++) {
  40.         if (mint[max1[i-1]]<=seg[i].first) max1[i]=max1[i-1]+1; else max1[i]=max1[i-1];
  41.         mint[max1[i]]=min(mint[max1[i]],seg[i].second);
  42.     }
  43.         // до текущего момента mod был не нужен, сейчас его создаю чтобы пересчитывать ответ
  44.         int mod=998244353;
  45. // Сейчас будет гениальный ход, над которым надо подумать
  46. // cur[i] хранит как можно заметить 3 числа -
  47. //cur[i].first это max1[i],
  48. //cur[i].second.first это seg[i].second,
  49. //cur[i].second.second это seg[i].first
  50.     // в цикле снизу это явно показывается
  51.     vector <pair<int,pair<int,int>>> cur(a);
  52.    for (int i=0;i<a;i++) {
  53.        cur[i]={max1[i],{seg[i].second,seg[i].first}};
  54.    }
  55.    //сортирую этот вектор, теперь он отсортирован вначале по максимальному размеру набора, а потом по ПРАВОЙ границе
  56.    sort(cur.begin(),cur.end());
  57.    // меняю левую и правую границу каждого отрезка
  58.    for (int i=0;i<a;i++) swap(cur[i].second.first,cur[i].second.second);
  59.    // dp[i] - количество вариантов достичь максимальный набор используя отрезки от 0 до i (по модулю mod офк)
  60.    int dp[a];
  61.    // pref[i] - префиксная сумма динамик с таким же max1 как и у текущего. Именно вместо этого массива Сёма предлагал запилить двумерное ДО
  62.    int pref[a];
  63.    // пересчёт динамики и префикса для первого отрезка, так как на него ничего не влияет и всё очевидно
  64.    dp[0]=1;
  65.    pref[0]=1;
  66.    // l,r,mid будут использоваться в бинпоиске ниже, но я их вывел сюда
  67.    // Это я сделал потому что иначе они будут создаваться больше миллиона раз на макс тесте
  68.    int l,r,mid;
  69.    //border - сложная фигня, но идейная
  70.    // border[i] - номер правого элемента, у которого max1==i
  71.    // Этот массив будет использоваться в бинпоиске для определения границ - без него ловил wa как ни задавал границы
  72.    int border[a+1];
  73.    //определние border[1] для первого отрезка типа базы индукции
  74.    border[1]=0;
  75.    //цикл снизу - пересчёт динамик, префиксов и границ
  76.    for (int i=1;i<a;i++) {
  77.        // случай 1 - текущий отрезок нельзя приставить ни к какому другому, а именно max1[i]=1
  78.        // в таком случае - пересчитываем dp, pref, border очевидно как; иначе пойдёт по else и уже будет делать бинпоиск
  79.        if (cur[i].first==1) { dp[i]=1; pref[i]=pref[i-1]+1; border[1]=i; } else {
  80.            //пересчёт раницы
  81.            border[cur[i].first]=i;
  82.            //определение границ, почему так?
  83.            // Подумай сам, если не получилось то можешь прочитать строку внизу.
  84.            // текущий отрезок имеет номер i. Как мы задавали, размер максимального набора с его использованием - cur[i].first
  85.            // Так как я сортировал по cur.first вначале (так работает сортировка, а я это просто использовал в своих нуждах), но
  86.            //имеет смысл перебирать только предыдущие отрезки, для которых cur[j].first==cur[i].first-1
  87.            // Они лежат в границе от l до r включительно (вроде очевидно)
  88.            if (cur[i].first!=2) l=border[cur[i].first-2]+1; else l=0;
  89.            r=border[cur[i].first-1];
  90.            // мне лень писать доказательство монотонности (точнее почему будет работать бинпоиск),
  91.            // поэтому подумай над этим сам. Если не придумаешь и будет интересно, я напишу в лс  
  92.            while (r-l>1) {
  93.                mid=(l+r)/2;
  94.                if (cur[mid].first==cur[i].first || cur[mid].second.second>cur[i].second.first) r=mid-1; else l=mid;
  95.            }
  96.            if (cur[r].first<cur[i].first && cur[r].second.second<=cur[i].second.first) l=r;
  97.            // собственно сам бинпоиск, теперь в l хранится номер самого подходящего отрезка
  98.            // Какой вообще отрезок искался -
  99.            //для которого правая граница не больше, чем левая у текушего
  100.            //Теперь пересчёт динамики очевиден
  101.            dp[i]=pref[l];
  102.            //Пересчёт префикса по определению
  103.            if (cur[i].first==cur[i-1].first) pref[i]=pref[i-1]+dp[i]; else pref[i]=dp[i];
  104.            // Взятие префикса по модулю чтобы не вылетело из-за переполнения
  105.            pref[i]%=mod;
  106.           // cout<<i<<" "<<l<<" "<<dp[i]<<" "<<cur[i].first<<" "<<cur[i].second.first<<" "<<cur[i].second.second<<" "<<pref[i]<<"\n";
  107.        }
  108.    }
  109.    // так как max1 - монотонна (из-за того, что сверху была сортировка),
  110.    //то в pref[a-1] будет храниться сумма всех динамик для максимального размера набора - это именно то, что нам и нужно
  111.    cout<<pref[a-1];
  112.     return 0;
  113. }
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