Cod sursa(job #2797652)

Utilizator andreic06Andrei Calota andreic06 Data 10 noiembrie 2021 13:23:10
Problema Arbori de intervale Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.98 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;
const int NMAX = 1e5;
struct segment_tree {
      int value[1 + 4 * NMAX];
      int sgt_size = 0;

      void init ( int node, int left, int right ) {
          if ( left == node )
            value[node] = 0;
          else {
            int mid = left + ( right - left ) / 2;
            init ( node * 2 + 1, left, mid );
            init ( node * 2 + 2, mid + 1, right );
            value[node] = 0;
          }
      }

      void update ( int node, int left, int right, int pos, int x ) {
          if ( left == right )
            value[node] = x;
          else {
            int mid = left + ( right - left ) / 2;
            if ( pos <= mid )
              update ( node * 2 + 1, left, mid, pos, x );
            else
              update ( node * 2 + 2, mid + 1, right, pos, x );
            value[node] = max ( value[node * 2 + 1], value[node * 2 + 2] );
          }
      }

      int query ( int node, int left, int right, int x, int y ) {
         if ( x <= left && right <= y )
           return value[node];
         int mid = left + ( right - left ) / 2;

         int answer = 0;
         if ( x <= mid )
           answer = max ( answer, query ( node * 2 + 1, left, mid, x, y ) );
         if ( mid + 1 <= y )
           answer = max ( answer, query ( node * 2 + 2, mid + 1, right, x, y ) );
         return answer;
      }
};

ifstream fin ( "scmax.in" );
ofstream fout ( "scmax.out" );
int n;
pair<int, int> aux[1 + NMAX];
int v[1 + NMAX];
void read () {
    fin >> n;
    for ( int i = 1; i <= n; i ++ ) {
       fin >> aux[i].first;
       aux[i].second = i;
    }
    sort ( aux + 1, aux + n + 1 );
    for ( int i = 1; i <= n; i ++ )
       if ( aux[i].first == aux[i - 1].first )
         v[aux[i].second] = v[aux[i - 1].second];
       else
         v[aux[i].second] = i;

    for ( int i = 1; i <= n; i ++ )
       swap ( aux[i].first, aux[i].second );
    sort ( aux + 1, aux + n + 1 );
}

int dp[1 + NMAX];
void solve () {
    segment_tree sgt; sgt.init ( 0, 0, n );
    for ( int i = 1; i <= n; i ++ ) {
       int answer = sgt.query ( 0, 0, n, 0, v[i] - 1 ) + 1;
       sgt.update ( 0, 0, n, v[i], answer );
       dp[i] = answer;
    }
}

void print_answer () {
    int maxx = 0; int last;
    for ( int i = 1; i <= n; i ++ ) {
       if ( maxx < dp[i] ) {
         maxx = dp[i];
         last = i;
       }
    }

    fout << maxx << "\n";

    vector<int> answer;
    answer.push_back ( aux[last].second );
    for ( int i = last - 1; i >= 1; i -- ) {
       if ( dp[i] + 1 == maxx && aux[i].second < aux[last].second ) {
         answer.push_back ( aux[i].second );
         last = i;
         maxx --;
       }
    }

    reverse ( answer.begin (), answer.end () );
    for ( auto x : answer )
       fout << x << " ";
}
int main()
{
   read ();
   solve ();
   print_answer ();
    return 0;
}