Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- using namespace std;
- signed main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- // сверху ничего особенного
- int a;
- cin>>a;
- vector <pair<int,int>> seg(a);
- for (int i=0;i<a;i++) cin>>seg[i].first>>seg[i].second;
- // а - количество отрезков
- // seg - вектор, в котором хранятся отрезки. seg[i].first - левая граница, seg[i].second - правая граница
- sort(seg.begin(),seg.end());
- //сортирую по левой границе, это делается встроенной сортировкой
- int mint[a+1];
- int max1[a];
- // ща будет сложное определение
- //Короче, max1[i] - максимальный размер набора который можно составить из первых i отрезков (в нулевой индексации)
- // Очевидно, что max1 - монотонный массив, то есть max1[i-1]<=max1[i]
- // Тогда, сделаем mint - массив, в котором хранится минимальное время,
- // на котором заканчивается последняя тренировка в каком-либо наборе размера i
- // задаю mint явно больше максимального значения
- for (int i=1;i<=a;i++) {
- mint[i]=1000000000000;
- }
- // первый отрезок очевидно как влияет на эти 2 массива, поэтому пересчитываю для первого отрезка - типа база индукции
- mint[1]=seg[0].second;
- max1[0]=1;
- // for (int i=0;i<a;i++) cout<<seg[i].first<<" "<<seg[i].second<<"\n";
- // цикл пересчёта этих массивов
- // что в нём происходит - очевидно, что max1[i]-max1[i-1]<=1 (если не очевидно, подумай почему)
- // Поэтому есть 2 варианта, которые разобраны в ифе.
- // В этом цикле явно всё пересчитывается, если вдуматься то становится понятно
- for (int i=1;i<a;i++) {
- if (mint[max1[i-1]]<=seg[i].first) max1[i]=max1[i-1]+1; else max1[i]=max1[i-1];
- mint[max1[i]]=min(mint[max1[i]],seg[i].second);
- }
- // до текущего момента mod был не нужен, сейчас его создаю чтобы пересчитывать ответ
- int mod=998244353;
- // Сейчас будет гениальный ход, над которым надо подумать
- // cur[i] хранит как можно заметить 3 числа -
- //cur[i].first это max1[i],
- //cur[i].second.first это seg[i].second,
- //cur[i].second.second это seg[i].first
- // в цикле снизу это явно показывается
- vector <pair<int,pair<int,int>>> cur(a);
- for (int i=0;i<a;i++) {
- cur[i]={max1[i],{seg[i].second,seg[i].first}};
- }
- //сортирую этот вектор, теперь он отсортирован вначале по максимальному размеру набора, а потом по ПРАВОЙ границе
- sort(cur.begin(),cur.end());
- // меняю левую и правую границу каждого отрезка
- for (int i=0;i<a;i++) swap(cur[i].second.first,cur[i].second.second);
- // dp[i] - количество вариантов достичь максимальный набор используя отрезки от 0 до i (по модулю mod офк)
- int dp[a];
- // pref[i] - префиксная сумма динамик с таким же max1 как и у текущего. Именно вместо этого массива Сёма предлагал запилить двумерное ДО
- int pref[a];
- // пересчёт динамики и префикса для первого отрезка, так как на него ничего не влияет и всё очевидно
- dp[0]=1;
- pref[0]=1;
- // l,r,mid будут использоваться в бинпоиске ниже, но я их вывел сюда
- // Это я сделал потому что иначе они будут создаваться больше миллиона раз на макс тесте
- int l,r,mid;
- //border - сложная фигня, но идейная
- // border[i] - номер правого элемента, у которого max1==i
- // Этот массив будет использоваться в бинпоиске для определения границ - без него ловил wa как ни задавал границы
- int border[a+1];
- //определние border[1] для первого отрезка типа базы индукции
- border[1]=0;
- //цикл снизу - пересчёт динамик, префиксов и границ
- for (int i=1;i<a;i++) {
- // случай 1 - текущий отрезок нельзя приставить ни к какому другому, а именно max1[i]=1
- // в таком случае - пересчитываем dp, pref, border очевидно как; иначе пойдёт по else и уже будет делать бинпоиск
- if (cur[i].first==1) { dp[i]=1; pref[i]=pref[i-1]+1; border[1]=i; } else {
- //пересчёт раницы
- border[cur[i].first]=i;
- //определение границ, почему так?
- // Подумай сам, если не получилось то можешь прочитать строку внизу.
- // текущий отрезок имеет номер i. Как мы задавали, размер максимального набора с его использованием - cur[i].first
- // Так как я сортировал по cur.first вначале (так работает сортировка, а я это просто использовал в своих нуждах), но
- //имеет смысл перебирать только предыдущие отрезки, для которых cur[j].first==cur[i].first-1
- // Они лежат в границе от l до r включительно (вроде очевидно)
- if (cur[i].first!=2) l=border[cur[i].first-2]+1; else l=0;
- r=border[cur[i].first-1];
- // мне лень писать доказательство монотонности (точнее почему будет работать бинпоиск),
- // поэтому подумай над этим сам. Если не придумаешь и будет интересно, я напишу в лс
- while (r-l>1) {
- mid=(l+r)/2;
- if (cur[mid].first==cur[i].first || cur[mid].second.second>cur[i].second.first) r=mid-1; else l=mid;
- }
- if (cur[r].first<cur[i].first && cur[r].second.second<=cur[i].second.first) l=r;
- // собственно сам бинпоиск, теперь в l хранится номер самого подходящего отрезка
- // Какой вообще отрезок искался -
- //для которого правая граница не больше, чем левая у текушего
- //Теперь пересчёт динамики очевиден
- dp[i]=pref[l];
- //Пересчёт префикса по определению
- if (cur[i].first==cur[i-1].first) pref[i]=pref[i-1]+dp[i]; else pref[i]=dp[i];
- // Взятие префикса по модулю чтобы не вылетело из-за переполнения
- pref[i]%=mod;
- // cout<<i<<" "<<l<<" "<<dp[i]<<" "<<cur[i].first<<" "<<cur[i].second.first<<" "<<cur[i].second.second<<" "<<pref[i]<<"\n";
- }
- }
- // так как max1 - монотонна (из-за того, что сверху была сортировка),
- //то в pref[a-1] будет храниться сумма всех динамик для максимального размера набора - это именно то, что нам и нужно
- cout<<pref[a-1];
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement