Pagini recente » Cod sursa (job #295492) | Cod sursa (job #75851) | Cod sursa (job #2892210) | Cod sursa (job #1989348) | Cod sursa (job #2265346)
#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;
}