Advertisement
Guest User

Untitled

a guest
Jun 27th, 2019
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.55 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement