Submission #1253179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253179		QwertyPi	Obstacles for a Llama (IOI25_obstacles)	C++20	24 / 100	246 ms	34892 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 2e5 + 11;

struct MM {
    MM(int x) : mx(x), mn(x) {};
    MM(int x, int y) : mx(x), mn(y) {};
    int mx, mn;
    MM operator+ (const MM& o) const {
        return MM(max(mx, o.mx), min(mn, o.mn));
    }
};

struct SegTree {
    int T[N_MAX << 2];
    void build(vector<int>& A, int v, int l, int r) {
        if (l == r) T[v] = A[l];
        else {
            int m = (l + r) / 2;
            build(A, v * 2 + 1, l, m);
            build(A, v * 2 + 2, m + 1, r);
            T[v] = max(T[v * 2 + 1], T[v * 2 + 2]);
        }
    }
    int query(int ql, int qr, int v, int l, int r) {
        if (ql <= l && r <= qr) return T[v];
        if (qr < l || r < ql) return -1;
        int m = (l + r) / 2;
        int qa = query(ql, qr, v * 2 + 1, l, m);
        int qb = query(ql, qr, v * 2 + 2, m + 1, r);
        return max(qa, qb);
    }
} ST;

struct DSU {
    vector<MM> M; vector<int> P, life, L, R;
    DSU () = default;
    DSU (vector<int> H) {
        int N = H.size();
        for (int i = 0; i < N; i++) {
            M.push_back(H[i]);
            P.push_back(i);
            L.push_back(i);
            R.push_back(i);
            life.push_back(1);
        }
    }
    int f(int x) { return x == P[x] ? x : P[x] = f(P[x]); }
    void g(int x, int y) {
        x = f(x), y = f(y); if (x == y) return;
        M[x] = M[x] + M[y]; P[y] = x; life[x] += life[y];
        L[x] = min(L[x], L[y]), R[x] = max(R[x], R[y]);
    }
    MM h(int x) {
        return M[f(x)];
    }
};

DSU dsu;

int lowest[N_MAX];

vector<int> T, H;

void initialize(vector<int> T, vector<int> H) {
    ::T = T; ::H = H; T.push_back(0);
    int N = T.size(), M = H.size();
    dsu = DSU(H); ST.build(H, 0, 0, M - 1);
    set<pair<int, int>> high, low;
    for (int i = 0; i < M - 1; i++) {
        high.insert({max(H[i], H[i + 1]), i});
    }
    for (int i = 0; i < M; i++) {
        low.insert({H[i], i});
    }
    for (int i = 0; i < N; i++) {
        // cout << "H " << i << endl;
        while (!high.empty() && high.begin()->first < T[i]) {
            int x = high.begin()->second;
            dsu.g(x, x + 1);
            high.erase(high.begin());
        }
        while (!low.empty() && low.begin()->first >= T[i]) {
            int x = low.begin()->second;
            int y = dsu.f(x);
            // cout << dsu.life[y] << ' ' << dsu.L[y] << ' ' << dsu.R[y] << endl;
            if (--dsu.life[y] == 0) {
                for (int j = dsu.L[y]; j <= dsu.R[y]; j++) {
                    lowest[j] = i - 1;
                }
            }
            low.erase(low.begin());
        }
    }
}

bool can_reach(int L, int R, int S, int D) {
    if (S > D) swap(S, D);
    int maxH = ST.query(S, D, 0, 0, (int) H.size() - 1);
    int req = upper_bound(T.begin(), T.end(), maxH) - T.begin();
    // cout << maxH << ' ' << T[0] << endl;
    return lowest[S] >= req && lowest[D] >= req;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17