Submission #1258181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258181		jamesbamber	Obstacles for a Llama (IOI25_obstacles)	C++20	83 / 100	173 ms	34104 KiB

obstacles

#include "obstacles.h"

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

struct segment {

    vector<pair<int,int>> tr_max;
    vector<int> tr_min;

    int sz = 1;
    int n;

    int MIN = -1e9 - 1;

    void build(int v, int l, int r, vector<int> &vec) {
        if(r-l == 1) {
            tr_max[v] = {vec[l], l};
            tr_min[v] = vec[l];
            return;
        }

        int m = (l+r)/2;

        build(2*v, l, m, vec);
        build(2*v+1, m, r, vec);

        tr_max[v] = max(tr_max[2*v], tr_max[2*v+1]);
        tr_min[v] = min(tr_min[2*v], tr_min[2*v+1]);
    }

    segment(vector<int> &v) {
        n = v.size();
        while(sz < n) sz *= 2;

        tr_max.assign(2*sz, {MIN, -1});
        tr_min.assign(2*sz, -MIN);

        build(1, 0, n, v);
    }

    pair<int,int> mx(int v, int l, int r, int ql, int qr) {
        if(l >= qr or r <= ql) return {MIN, -1};
        if(l >= ql and r <= qr) return tr_max[v];

        int m = (l+r)/2;
        return max(mx(2*v, l, m, ql, qr), mx(2*v+1, m, r, ql, qr));
    }

    pair<int,int> mx(int l, int r) {
        return mx(1, 0, n, l, r);
    }

    int nse(int v, int l, int r, int ql, int qr, int val) {
        if(l >= qr or r <= ql or tr_min[v] > val) return -1;
        if(r - l == 1) return l;

        int m = (l+r)/2;

        int x = nse(2*v, l, m, ql, qr, val);
        if(x != -1) return x;
        return nse(2*v+1, m, r, ql, qr, val);
    }

    int nse(int l, int r, int val) {
        return nse(1, 0, n, l, r, val);
    }

    int pse(int v, int l, int r, int ql, int qr, int val) {
        if(l >= qr or r <= ql or tr_min[v] > val) return -1;
        if(r - l == 1) return l;

        int m = (l+r)/2;

        int x = pse(2*v+1, m, r, ql, qr, val);
        if(x != -1) return x;
        return pse(2*v, l, m, ql, qr, val);
    }

    int pse(int l, int r, int val) {
        return pse(1, 0, n, l, r, val);
    }
};

vector<int> cc;

void initialize(std::vector<int> T, std::vector<int> H) {

    int N = T.size(), M = H.size();

    segment vert(T);

    vector<int> max_T(M);
    for(int i=0; i<M; i++) {
        int r = vert.nse(0, N, H[i]);
        if(r == -1) r = N;
        max_T[i] = vert.mx(0, r).first;

    }

    // for(int x: vert.tr_min) cout << x << endl;

    auto neg_H = H;
    for(int i=0; i<M; i++) neg_H[i] = -H[i];

    segment hor(neg_H);

    vector<vector<int>> ad(M);

    for(int i=0; i<M; i++) { 

        int l = hor.pse(0, i+1, -max_T[i]);
        if(l == -1) l = -1;

        int r = hor.nse(i, M, -max_T[i]);
        if(r == -1) r = M;

        int j = hor.mx(l+1, r).second;

        // cerr << "range: " << l << " " << r << endl;
        // cerr << i << " " << j << endl;

        if(j == -1) continue; 
        if(H[j] > H[i]) continue;


        ad[i].push_back(j);
        ad[j].push_back(i);
    }

    vector<int> vis(M);
    auto dfs = [&](auto &&self, int v, int c) -> void {
        vis[v] = 1;
        cc[v] = c;
        
        for(int u: ad[v]) {
            if(vis[u]) continue;
            self(self, u, c);
        }
    };

    int ct = 0;
    cc.resize(M);

    for(int i=0; i<M; i++) {
        if(vis[i]) continue;
        dfs(dfs, i, ct++);
    }
}

bool can_reach(int L, int R, int S, int D) {
    return cc[S] == cc[D];
}

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