Submission #1095208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095208		RiverFlow	September (APIO24_september)	C++17	100 / 100	303 ms	37320 KiB

september

#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b or a == -1) { a = b; return 1; } return 0;
}

const int N = (int)1e5 + 9;
const int mod = (int)1e9 + 7;

int n, m;

int mx[N], a[5][N], L[N], R[N];

vector<int> g[N];

void dfs(int u, int p) {
    mx[u] = R[u];
    for(int v : g[u]) if (v != p) {
        dfs(v, u);
        mx[u] = max(mx[u], mx[v]);
    }
}

const int LG = 16;

struct segment_tree {
    int n;
    const int INF = -(int)1e6;
    vector<int> t, lz;
    segment_tree () {};
    segment_tree (int _n) {
        n = _n;
        t.resize(4 * n + 7);
        lz.resize(4 * n + 7);
    }
    void set_off(int id, int l, int r, int u, int v) {
        if (l > v or r < u) return ;
        if (l >= u and r <= v) {
            t[id] = INF;
            lz[id] = -1;
            return ;
        }
        if (lz[id] == -1) {
            t[id << 1] = t[id << 1 | 1] = INF;
            lz[id << 1] = lz[id << 1 | 1] = -1;
            lz[id] = 0;
        }
        int m = (l + r) >> 1;
        set_off(id << 1, l, m, u, v);
        set_off(id << 1 | 1, m + 1, r, u, v);
        t[id] = max(t[id << 1], t[id << 1 | 1]);
    }
    void set_off(int l, int r) {
        ++l, ++r;
        set_off(1, 1, n, l, r);
    }
    void update(int id, int l, int r, int p, int val) {
        if (l == r) return void(t[id] = val);
        if (lz[id] == -1) {
            t[id << 1] = t[id << 1 | 1] = INF;
            lz[id << 1] = lz[id << 1 | 1] = -1;
            lz[id] = 0;
        }
        int m = (l + r) >> 1;
        if (p <= m)
            update(id << 1, l, m, p, val);
        else
            update(id << 1 | 1, m + 1, r, p, val);
        t[id] = max(t[id << 1], t[id << 1 | 1]);
    }
    void set_on(int p, int val) {
        ++p;
        update(1, 1, n, p, val);
    }
    int get(int id, int l, int r, int u, int v) {
        if (l > v or r < u) return 0;
        if (l >= u and r <= v) return t[id];
        if (lz[id] == -1) {
            t[id << 1] = t[id << 1 | 1] = INF;
            lz[id << 1] = lz[id << 1 | 1] = -1;
            lz[id] = 0;
        }
        int m = (l + r) >> 1;
        return max(get(id << 1, l, m, u, v),
                   get(id << 1 | 1, m + 1, r, u, v));
    }
    int get(int l, int r) {
        ++l, ++r;
        return get(1, 1, n, l, r);
    }
};

int sp[N][LG + 1], lg[N];

int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
    n = N, m = M;

    FOR(i, 0, n - 1) {
        g[i].clear();
        L[i] = n;
        R[i] = mx[i] = 0;
    }

    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < n - 1; ++j)
            a[i][j] = S[i][j];
    }

    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < n - 1; ++j) {
            maxi(R[a[i][j]], j);
            mini(L[a[i][j]], j);
        }
    }

    FOR(i, 1, n - 1) {
        g[F[i]].push_back(i);
    }

    dfs(0, -1);
    vector<int> d(n, 0);

    vector<int> dp(n, -1);

    FOR(i, 0, n - 1) {
        d[i] = n;
        for(int t = 0; t < m; ++t) {
            mini(d[i], L[a[t][i]]);
        }
    }
    auto get = [&](int l, int r) {
        int j = lg[r - l + 1];
        return max(sp[l][j], sp[r - (1 << j) + 1][j]);
    };
    for(int i = 0; i < n - 1; ++i) {
        sp[i][0] = mx[a[0][i]];
    }
    for(int j = 1; (1 << j) < n; ++j)
    for(int i = 0; i + (1 << j) - 1 < n; ++i) {
        sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
    }
    FOR(i, 2, n) lg[i] = lg[i / 2] + 1;

    stack<int> st;

    segment_tree IT(n);

    for(int i = 0; i < n - 1; ++i) {
        int lb = 0, rb = i;
        int r = i + 1;
        while (lb <= rb) {
            int mid = (lb + rb) >> 1;
            if (get(mid, i) <= i) {
                r = mid;
                rb = mid - 1;
            } else
                lb = mid + 1;
        }
        while (st.size()) {
            int u = st.top();
            if (d[u] > d[i]) {
                st.pop();
            } else
                break ;
        }
        int b = (st.size() ? st.top() + 1 : 1);

        IT.set_off(b, i);
        if (b == d[i]) {
            if (b == 0 or dp[b - 1] != -1)
                IT.set_on(b, (b > 0 ? dp[b - 1] : 0));
        }

        st.push(i);

        if (r <= i and get(0, i) <= i) {
            maxi(dp[i], IT.get(r, i) + 1);
        }
    }
	return dp[n - 2];
}

#ifdef LOCAL
void taskcase() {
	int N, M;
	assert(2 == scanf("%d%d", &N, &M));

	std::vector<int> F(N);
	F[0] = -1;
	for (int i = 1; i < N; ++i)
  		assert(1 == scanf("%d", &F[i]));

	std::vector<std::vector<int>> S(M, std::vector<int>(N - 1));
	for (int i = 0; i < M; ++i)
		for (int j = 0; j < N - 1; ++j)
  			assert(1 == scanf("%d", &S[i][j]));

	printf("%d\n", solve(N, M, F, S));
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    freopen("main.inp", "r", stdin);
    freopen("main.out", "w", stdout);
	int T;
	assert(1 == scanf("%d", &T));
	while(T--) taskcase();
	return 0;
}

#endif

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 5 / 5
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 11 / 11
• Subtask 7: 9 / 9
• Subtask 8: 11 / 11
• Subtask 9: 9 / 9
• Subtask 10: 16 / 16