Codeforces Round #410 (Div. 2), problem: (E) Mike and code of a permutation Solution In C/C++

#pragma warning(disable:4996)

#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <complex>
#include <iterator>
#include <random>
#include <time.h>
#include <tuple>
#include <functional>
#include <list>
#include <limits.h>
#define mp make_pair
#define ni(x) scanf(“%d”, &(x))
#define nii(x,y) scanf(“%d%d”,&(x),&(y))
#define mul(x,y) ((ll)(x)*(y)%mod)
#define mtp make_tuple
#define F(i,n) for(int i = 0; i < (n); i++)
#define FF(i,n) for(int i = 1; i <= (n); i++)
#define FE(i,n) for(int i = 0; i <= (n); i++)

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int mod = 1000000007;
const int inf = 2012345678;
const ll infl = 9012345678901234567;
const double pi = 3.1415926535897932384626433832795;
//—————————————————————————-//

const int N = 500010;
set<pii> tr[N];
int a[N], chk[N], res[N], clk, b[N];

void upd(pii x, int i, int n) {
while (i <= n) {
tr[i].insert(x);
i += i&(-i);
}
}
int n;
void dfs(int u) {
chk[u] = 1;
if (a[u] != inf) if(!chk[a[u]])dfs(a[u]);

int x = b[u];
x–;
if (b[u] == -1) x = n;
while (x) {
while (1) {
auto it = tr[x].lower_bound(pii(u, 0));
if (it != tr[x].end()) {
int v = it->second;
tr[x].erase(it);
if(!chk[v])dfs(v);
}
else break;
}
x -= x&(-x);
}

res[u] = clk++;
}

int main() {
#ifndef __GNUG__
freopen(“input.txt”, “r”, stdin);
#endif
ni(n);
FF(i, n)ni(a[i]);
FF(i, n)b[i] = -1;
FF(i, n) {
if (a[i] == -1) a[i] = inf;
else b[a[i]] = i;
upd(pii(a[i], i), i, n);
}
FF(i, n)if (!chk[i])dfs(i);
FF(i, n)printf(“%d “, n – res[i]); puts(“”);
return 0;
}

#pragma warning(disable:4996)

#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <complex>
#include <iterator>
#include <random>
#include <time.h>
#include <tuple>
#include <functional>
#include <list>
#include <limits.h>
#define mp make_pair
#define ni(x) scanf(“%d”, &(x))
#define nii(x,y) scanf(“%d%d”,&(x),&(y))
#define mul(x,y) ((ll)(x)*(y)%mod)
#define mtp make_tuple
#define F(i,n) for(int i = 0; i < (n); i++)
#define FF(i,n) for(int i = 1; i <= (n); i++)
#define FE(i,n) for(int i = 0; i <= (n); i++)

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int mod = 1000000007;
const int inf = 2012345678;
const ll infl = 9012345678901234567;
const double pi = 3.1415926535897932384626433832795;
//—————————————————————————-//

const int N = 500010;
set<pii> tr[N];
int a[N], chk[N], res[N], clk, b[N];

void upd(pii x, int i, int n) {
while (i <= n) {
tr[i].insert(x);
i += i&(-i);
}
}
int n;
void dfs(int u) {
chk[u] = 1;
if (a[u] != inf) if(!chk[a[u]])dfs(a[u]);

int x = b[u];
x–;
if (b[u] == -1) x = n;
while (x) {
while (1) {
auto it = tr[x].lower_bound(pii(u, 0));
if (it != tr[x].end()) {
int v = it->second;
tr[x].erase(it);
if(!chk[v])dfs(v);
}
else break;
}
x -= x&(-x);
}

res[u] = clk++;
}

int main() {
#ifndef __GNUG__
freopen(“input.txt”, “r”, stdin);
#endif
ni(n);
FF(i, n)ni(a[i]);
FF(i, n)b[i] = -1;
FF(i, n) {
if (a[i] == -1) a[i] = inf;
else b[a[i]] = i;
upd(pii(a[i], i), i, n);
}
FF(i, n)if (!chk[i])dfs(i);
FF(i, n)printf(“%d “, n – res[i]); puts(“”);
return 0;
}