Cod sursa(job #2267131)

Utilizator retrogradLucian Bicsi retrograd Data 23 octombrie 2018 12:10:48
Problema Subsir 2 Scor 69
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <bits/stdc++.h>

using namespace std;

template<typename T>
struct SegmTree {
  vector<T> data; int n;
  const T kInf;

  SegmTree(int n, T kInf) : data(2 * n, kInf), n(n), kInf(kInf) {}
  
  void Update(int pos, T val) {
    for (data[pos += n] = val; pos > 1; pos /= 2)
      data[pos / 2] = min(data[pos], data[pos ^ 1]);
  }
  
  T Query(int b, int e) {
    T res = kInf;
    for (b += n, e += n; b < e; b /= 2, e /= 2) {
      if (b % 2) res = min(res, data[b++]);
      if (e % 2) res = min(res, data[--e]);
    }
    return res;
  }
};

int main() {
    ifstream cin("subsir2.in");
    ofstream cout("subsir2.out");

    int n; cin >> n;
    vector<int> v(n), stk;
    vector<pair<int, int>> order(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
        order[i] = {v[i], i};
    }
    sort(order.begin(), order.end());
    for (int i = 0; i < n; ++i) {
        auto it = lower_bound(order.begin(), order.end(), make_pair(v[i], i));
        v[i] = distance(order.begin(), it);
    }
    
    vector<vector<int>> solve(n);
    vector<int> dp(n, 0), prv(n, -1);

    for (int i = 0; i < n; ++i) {
        while (stk.size() && v[stk.back()] > v[i])
            stk.pop_back();
        if (stk.size())
            solve[stk.back()].push_back(i);
        stk.push_back(i);
    }

    const tuple<int, int, int> kInf = {2e9, n, n};
    SegmTree<tuple<int, int, int>> st(n, kInf);

    stk.clear();
    for (int i = 0; i < n; ++i) {
        while (stk.size() && v[stk.back()] <= v[i]) {
            st.Update(stk.back(), kInf);
            stk.pop_back();
        }
        st.Update(i, {dp[i], v[i], i});
        stk.push_back(i);

        for (auto j : solve[i]) {
            int start = *lower_bound(
                stk.begin(), stk.end(), j, [&](int a, int b) {
                    return v[a] > v[b]; 
            });
            tie(dp[j], ignore, prv[j]) = st.Query(start, n);
            dp[j] += 1;
        }
    }
    
    vector<int> ans;
    for (int pos = get<2>(st.Query(0, n)); pos >= 0; pos = prv[pos])
        ans.push_back(pos);
    reverse(ans.begin(), ans.end());
    
    cout << ans.size() << endl;
    for (auto x : ans) 
        cout << x + 1 << " "; 
    cout << endl;

    return 0;
}