Submission #12637772

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
typedef int V;
// NV=3010101 -> 38MB
#define NV 6010101
#define def 0
struct PersistentSegmentTree { //[L,R)
    V comp(V a, V b) { return max(a,b); }




    // -- template ---------------------
    struct S { int l, r; V x; } v[NV];
    int cnt = 1, n = -1;
    void init(int _n) { n = _n; rep(i, 0, NV) v[i].l = v[i].r = 0, v[i].x = def; }
    void add(int &root, int l, int r, int i, int val) {
        v[cnt] = v[root]; root = cnt++;if (l + 1 == r) { v[root].x += val; return; }
        int mi = (l + r) / 2;if (i < mi) add(v[root].l, l, mi, i, val);
        else add(v[root].r, mi, r, i, val);
        v[root].x = comp(v[v[root].l].x, v[v[root].r].x);}
    void add(int &root, int i, int val) { assert(0 < n);add(root, 0, n, i, val); }
    void update(int &root, int l, int r, int i, int val) {v[cnt] = v[root];root = cnt++;
        if (l + 1 == r) {v[root].x = val;return;}int mi = (l + r) / 2;
        if (i < mi) update(v[root].l, l, mi, i, val);else update(v[root].r, mi, r, i, val);
        v[root].x = comp(v[v[root].l].x, v[v[root].r].x);}
    void update(int &root, int i, int val) {assert(0 < n);update(root, 0, n, i, val);}
    V allget(int root) { assert(0 < n); return v[root].x;}
    V get(int root, int l, int r, int L, int R) {
        if (l >= r) return def;if (l == L && r == R) return v[root].x;int mi = (L + R) / 2;
        V le = get(v[root].l, max(l, L), min(r, mi), L, mi);
        V ri = get(v[root].r, max(l, mi), min(r, R), mi, R);return comp(le, ri);}
    V get(int root, int l, int r) {assert(0 < n);return get(root, l, r, 0, n);}
};
vector<int> compress1(int* v, int n) {
    vector<int> dic;
    rep(i, 0, n) dic.push_back(v[i]);
    sort(all(dic));
    dic.erase(unique(all(dic)), dic.end());
    rep(i, 0, n) v[i] = lower_bound(all(dic), v[i]) - dic.begin();
    return dic;
}
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














int N, a[201010];
vector<int> E[201010];
//---------------------------------------------------------------------------------------------------
PersistentSegmentTree pst;
int ans[201010];
void dfs(int cu = 0, int pa = -1, int root = 0) {
    int root2 = root;
    int ma = pst.get(root, 0, a[cu]);
    pst.update(root2, a[cu], max(pst.get(root, a[cu], a[cu] + 1), ma + 1));

    ans[cu] = pst.get(root2, 0, N);
    fore(to, E[cu]) if (to != pa) dfs(to, cu, root2);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> a[i];
    compress1(a, N);

    rep(i, 0, N - 1) {
        int u, v; cin >> u >> v;
        u--; v--;
        E[u].push_back(v);
        E[v].push_back(u);
    }

    pst.init(N);
    dfs();

    rep(i, 0, N) printf("%d\n", ans[i]);
}

Submission Info

Compile Error

./Main.cpp: In member function ‘V PersistentSegmentTree::get(int, int, int, int, int)’:
./Main.cpp:39:9: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   39 |         if (l >= r) return def;if (l == L && r == R) return v[root].x;int mi = (L + R) / 2;
      |         ^~
./Main.cpp:39:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
   39 |         if (l >= r) return def;if (l == L && r == R) return v[root].x;int mi = (L + R) / 2;
      |                                ^~

Judge Result