Pagini recente » Cod sursa (job #2101002) | Cod sursa (job #2637220) | Cod sursa (job #434682) | Cod sursa (job #2145000) | Cod sursa (job #2467685)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
int v[MAXN], arb[4 * MAXN];
vector<int> ans;
int n;
int query(int nod, int st, int dr, int a, int b){
if(a <= st && dr <= b) return arb[nod];
int mij = (st + dr) / 2, leftans = n + 1, rightans = n + 1;
if(a <= mij) leftans = query(2 * nod, st, mij, a, b);
if(b > mij) rightans = query(2 * nod + 1, mij + 1, dr, a, b);
if(v[leftans] < v[rightans]) return leftans;
else return rightans;
}
void update(int nod, int st, int dr, int a, int b){
if(st == dr && st == a){
arb[nod] = b;
return;
}
int mij = (st + dr) / 2;
if(a <= mij) update(2 * nod, st, mij, a, b);
else update(2 * nod + 1, mij + 1, dr, a, b);
if(v[arb[2 * nod]] < v[arb[2 * nod + 1]]) arb[nod] = arb[2 * nod];
else arb[nod] = arb[2 * nod + 1];
}
void lookscm(int nod, int st, int dr){
if(st >= dr) return;
while(v[arb[nod]] <= v[ans.back()]){
nod = 2 * nod + 1;
int mij = (st + dr) / 2;
st = mij + 1;
}
ans.push_back(arb[nod]);
lookscm(nod, st, dr);
}
int main()
{
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
fin >> n;
for(int i = 1; i <= 4 * n; ++i) arb[i] = n + 1;
v[n + 1] = 1e9;
for(int i = 1; i <= n; ++i){
fin >> v[i];
update(1, 1, n, i, i);
}
ans.push_back(0);
lookscm(1, 1, n);
ans.erase(ans.begin());
fout << ans.size() << "\n";
for(auto x:ans) fout << x << " ";
return 0;
}