Cod sursa(job #2265346)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 20 octombrie 2018 23:23:53
Problema Subsir 2 Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("subsir2.in");
ofstream out("subsir2.out");

const int NMAX = 5005;
const int VALMAX = 1000001;

int v[NMAX], dp[NMAX], aint[8 * VALMAX], maxpref[NMAX];

void update(int pos, int val, int node, int le, int ri) {
    if(le == ri)
        aint[node] = max(aint[node], val);
    else {
        int mid = (le + ri) / 2;
        if(pos <= mid)
            update(pos, val, node * 2, le, mid);
        else
            update(pos, val, node * 2 + 1, mid + 1, ri);
        aint[node] = max(aint[node * 2], aint[node * 2 + 1]);
    }
}

int query(int from, int to, int node, int le, int ri) {
    if(from <= le && ri <= to)
        return aint[node];
    int mid = (le + ri) / 2;
    int ans = 0;
    if(from <= mid)
        ans = query(from, to, node * 2, le, mid);
    if(mid < to)
        ans = max(ans, query(from, to, node * 2 + 1, mid + 1, ri));
    return ans;
}

struct Data {
    int x, y;
    bool operator< (Data other) const {
        if(x == other.x)
            return y < other.y;
        return x < other.x;
    }
};

int main() {
    int n;
    in >> n;
    maxpref[0] = -VALMAX;
    for(int i = 1; i <= n; i ++) {
        in >> v[i];
        maxpref[i] = max(v[i], maxpref[i - 1]);
    }

    int scmax = 0;
    maxpref[0] = 2 * VALMAX + 5;
    for(int i = n; i >= 1; i --) {
        dp[i] = 1 + query(v[i] + VALMAX, 2 * VALMAX, 1, 1, 2 * VALMAX);
        update(v[i] + VALMAX, dp[i], 1, 1, 2 * VALMAX);
        if(scmax < dp[i] && maxpref[i - 1] > v[i])
            scmax = dp[i];
    }
    out << scmax << "\n";

    int last = 0;
    v[0] = - VALMAX;
    v[n + 1] = 2 * VALMAX + 5;
    while(scmax > 0) {
        int curr = n + 1;
        for(int i = last + 1; i <= n; i ++)
            if(dp[i] == scmax && v[i] >= v[last] && v[curr] > v[i])
                curr = i;
        last = curr;
        out << last << " ";
        scmax --;
    }
    return 0;
}