Submission #1253289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253289		NekoRolly	Obstacles for a Llama (IOI25_obstacles)	C++20	21 / 100	76 ms	23112 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){
        t[find(a)] = find(b);
    }
} dsu;

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

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);

    for (int i=1; i<=n; i++){
        if (a[1] <= b[i]) continue;

        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))
            dsu.join(j, i);

        j = bR[i];
        if (j != m+1 && max_t > spt.query(i, j))
            dsu.join(i, j);
    }
}


bool can_reach(int L, int R, int S, int D) {
    return dsu.find(S+1) == dsu.find(D+1);
}

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