제출 #1253318

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253318		NekoRolly	Obstacles for a Llama (IOI25_obstacles)	C++20	0 / 100	2098 ms	82352 KiB

obstacles

#include "obstacles.h"
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;

const int N = 2e5+4;
const int inf = 1e9+4;

struct Sparce_Table{
    int t[N][18];

    void build(int n,int a[]){
        for (int i=1; i<=n; i++)
            t[i][0] = a[i];
        for (int j=0; j<17; j++)
            for (int i=1; i<=n; i++)
                t[i][j+1] = max(t[i][j], t[min(n, i+(1<<j))][j]);
    }

    int query(int l,int r){
        int k = 31 - __builtin_clz(r-l+1);
        return max(t[l][k], t[r-(1<<k)+1][k]);
    }
} spt;

struct Dsu{
    int t[N];

    void build(int n){
        for (int i=1; i<=n; i++) t[i] = i;
    }

    int find(int x){
        if (x == t[x]) return x;
        return t[x] = find(t[x]);
    }

    void join(int a,int b){
        // cout << a << " " << b << "\n";
        t[find(a)] = find(b);
    }
} dsu;


struct edge{
    int a,b,len;

    bool operator<(edge x){
        return len < x.len;
    }
};

int n,m;
int a[N],b[N];
int mx[N],mn[N];
int bL[N],bR[N];

vector<int> adj[N];
int cur,L[N],R[N];
int up[N][18],Max[N][18],Min[N][18];
int h[N];

void dfs(int u,int p){
    L[u] = cur++;
    up[u][0] = p;
    h[u] = h[p] + 1;
    Max[u][0] = Min[u][0] = u;
    for (int i=1; i<18; i++){
        up[u][i] = up[up[u][i-1]][i-1];
        Max[u][i] = max(Max[u][i-1], Max[up[u][i-1]][i-1]);
        Min[u][i] = min(Min[u][i-1], Min[up[u][i-1]][i-1]);
    }
    for (int v : adj[u])
        if (v != p)
            dfs(v, u);
    R[u] = cur;
}

bool isa(int a,int b){
    return L[a] <= L[b] && R[b] <= R[a];
}

int lca(int a,int b){
    if (isa(a, b)) return a;
    if (isa(b, a)) return b;
    for (int i=17; i>=0; i--)
        if (!isa(up[a][i], b))
            a = up[a][i];
    return up[a][0];
}

int get_max(int u,int k){
    int ans = -inf;
    for (int i=0; i<18; i++)
        if (k>>i&1){
            ans = max(ans, Max[u][i]);
            u = up[u][i];
        }
    return ans;
}

int get_min(int u,int k){
    int ans = inf;
    for (int i=0; i<18; i++)
        if (k>>i&1){
            ans = min(ans, Min[u][i]);
            u = up[u][i];
        }
    return ans;
}

void initialize(vector<int> T,vector<int> H){
    n = T.size(), m = H.size();

    mx[0] = -inf, mn[0] = inf;
    for (int i=1; i<=n; i++){
        a[i] = T[i-1];
        mx[i] = max(mx[i-1], a[i]);
        mn[i] = min(mn[i-1], a[i]);
    }

    for (int i=1; i<=m; i++)
        b[i] = H[i-1];
    b[0] = b[m+1] = -inf;

    stack<int> stk;

    stk.push(0);
    for (int i=1; i<=m; i++){
        while (b[stk.top()] > b[i]) stk.pop();
        bL[i] = stk.top();
        stk.push(i);
    }

    while (!stk.empty()) stk.pop();
    stk.push(m+1);
    for (int i=m; i>=1; i--){
        while (b[stk.top()] > b[i]) stk.pop();
        bR[i] = stk.top();
        stk.push(i);
    }

    spt.build(m, b);
    dsu.build(m);

    vector<edge> eds;
    for (int i=1; i<=m; i++){
        if (a[1] <= b[i]) continue;
        adj[0].push_back(i);

        int l = 1, r = n+1;
        while (l+1 < r){
            int md = (l+r)>>1;
            if (mn[md] > b[i]) l = md;
            else r = md;
        }

        int max_t = mx[l];

        int j = bL[i];
        if (j != 0 && max_t > spt.query(j, i))
            eds.push_back({j, i, i-j});

        j = bR[i];
        if (j != m+1 && max_t > spt.query(i, j))
            eds.push_back({i, j, j-i});
    }

    sort(eds.begin(), eds.end());

    for (auto [a, b, len] : eds){
        if (dsu.find(a) == dsu.find(b)) continue;
        dsu.join(a, b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    dfs(0, 0);
}


bool can_reach(int L, int R, int S, int D) {
    L++, R++, S++, D++;

    int l = lca(S, D);
    int ks = h[S] - h[l] + 1;
    int kd = h[D] - h[l] + 1;
    int maxi = max(get_max(S, ks), get_max(D, kd));
    int mini = min(get_min(S, ks), get_min(D, kd));
    return L <= mini && maxi <= R;
}

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