Advertisement
Dang_Quan_10_Tin

K-th LIS

Aug 8th, 2022
941
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.54 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. constexpr int N = 1e5 + 5;
  7. constexpr ll Inf = 2e18;
  8.  
  9. ll Mul(ll a, ll b)
  10. {
  11.     if (b == 0)
  12.         return 0;
  13.  
  14.     if (a > Inf / b)
  15.         return Inf;
  16.  
  17.     return a * b;
  18. }
  19.  
  20. ll Sum(ll a, ll b)
  21. {
  22.     if (a + b > Inf)
  23.         return Inf;
  24.     return a + b;
  25. }
  26.  
  27. struct SegmentTree
  28. {
  29.     int n;
  30.  
  31.     pair<int, ll> st[N * 4];
  32.  
  33.     SegmentTree()
  34.     {
  35.         fill_n(st, N * 4, make_pair(0, 1));
  36.     }
  37.  
  38.     pair<int, ll> Combine(const pair<int, ll> &a, const pair<int, ll> &b)
  39.     {
  40.         if (a.first > b.first)
  41.             return a;
  42.         else if (b.first > a.first)
  43.             return b;
  44.  
  45.         if (a.first == 0)
  46.             return a;
  47.  
  48.         return make_pair(a.first, Sum(a.second, b.second));
  49.     }
  50.  
  51.     void Update(int id, int l, int r, const int &x, const pair<int, ll> &v)
  52.     {
  53.         if (l > x || r < x)
  54.             return;
  55.         if (l == x && r == x)
  56.         {
  57.             st[id] = Combine(st[id], v);
  58.             return;
  59.         }
  60.  
  61.         Update(id << 1, l, (l + r) / 2, x, v);
  62.         Update(id << 1 | 1, (l + r) / 2 + 1, r, x, v);
  63.         st[id] = Combine(st[id << 1], st[id << 1 | 1]);
  64.     }
  65.  
  66.     void Update(int x, const pair<int, ll> &v)
  67.     {
  68.         Update(1, 1, n, x, v);
  69.     }
  70.  
  71.     pair<int, ll> Get(int id, int l, int r, const int &a, const int &b)
  72.     {
  73.         if (l > b || r < a)
  74.             return make_pair(0, 1);
  75.  
  76.         if (l >= a && r <= b)
  77.             return st[id];
  78.  
  79.         return Combine(Get(id << 1, l, (l + r) / 2, a, b), Get(id << 1 | 1, (l + r) / 2 + 1, r, a, b));
  80.     }
  81.  
  82.     pair<int, ll> Get(int l, int r)
  83.     {
  84.         return Get(1, 1, n, l, r);
  85.     }
  86. } f;
  87.  
  88. int n, a[N], b[N];
  89. ll dp[N], rdp[N];
  90. int res[N];
  91. vector<int> x[N];
  92.  
  93. ll k;
  94.  
  95. void Read()
  96. {
  97.     cin >> n >> k;
  98.  
  99.     for (int i = 1; i <= n; ++i)
  100.     {
  101.         cin >> a[i];
  102.         x[a[i]].emplace_back(i);
  103.     }
  104. }
  105.  
  106. void Solve()
  107. {
  108.     int ans = 0;
  109.  
  110.     f.n = n;
  111.     for (int i = n; i; --i)
  112.     {
  113.         pair<int, ll> v = f.Get(a[i] + 1, n);
  114.  
  115.         dp[i] = v.second;
  116.         b[i] = v.first + 1;
  117.         ans = max(ans, b[i]);
  118.  
  119.         f.Update(a[i], make_pair(b[i], dp[i]));
  120.     }
  121.  
  122.     x[0].emplace_back(0);
  123.     rdp[0] = 1;
  124.     b[0] = ans + 1;
  125.  
  126.     int val = 0;
  127.  
  128.     for (int i = ans; i; --i)
  129.     {
  130.         ll sum(0);
  131.  
  132.         for (int j = val + 1; j <= n; ++j)
  133.         {
  134.             int h = 0;
  135.             ll tmp = 0;
  136.             ll tmprdp = 0;
  137.  
  138.             for (auto t : x[j])
  139.             {
  140.                 while (h < (int)x[val].size() && x[val][h] <= t)
  141.                 {
  142.                     tmprdp = Sum(tmprdp, rdp[x[val][h]]);
  143.                     ++h;
  144.                 }
  145.  
  146.                 if (b[t] == i)
  147.                 {
  148.                     rdp[t] = tmprdp;
  149.                     tmp = Sum(tmp, Mul(dp[t], tmprdp));
  150.                 }
  151.             }
  152.            
  153.             if (Sum(sum, tmp) >= k)
  154.             {
  155.                 k -= sum;
  156.                 res[ans - i + 1] = j;
  157.                 val = j;
  158.  
  159.                 goto done;
  160.             }
  161.  
  162.             sum += tmp;
  163.         }
  164.  
  165.         cout << -1;
  166.         return;
  167.  
  168.     done:;
  169.         // cout << k << "\n";
  170.     }
  171.  
  172.     for (int i = 1; i <= ans; ++i)
  173.         cout << res[i] << " ";
  174. }
  175.  
  176. int32_t main()
  177. {
  178.     ios::sync_with_stdio(0);
  179.     cin.tie(0);
  180.     cout.tie(0);
  181.     if (fopen("kthlis.inp", "r"))
  182.     {
  183.         freopen("kthlis.inp", "r", stdin);
  184.         freopen("kthlis.out", "w", stdout);
  185.     }
  186.     Read();
  187.     Solve();
  188. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement