Submission #1299569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299569		takoshanava	Obstacles for a Llama (IOI25_obstacles)	C++20	83 / 100	254 ms	26436 KiB

obstacles

#include "obstacles.h"
#include "bits/stdc++.h"
#define pb push_back
#define fs first
#define sc second
using namespace std;
int const N = 2e5 + 10, LG = 19;
int rec[N];
bool dead[N], done[N];
int par[N];
int mn[N];
vector<int> ch[N];

struct segtree{
    int n;
    vector<int> t;
    void build(vector<int> &a) {
        n = a.size();
        t.assign(2 * n, 0);
        for (int i = 0; i < n; i++) t[i + n] = a[i];
        for (int i = n - 1; i > 0; i--) t[i] = max(t[i << 1], t[i << 1 | 1]);
    }
    int get(int l, int r) {
        l += n; r += n;
        int res = 0;
        while (l <= r) {
            if (l & 1) res = max(res, t[l++]);
            if (!(r & 1)) res = max(res, t[r--]);
            l >>= 1; r >>= 1;
        }
        return res;
    }
};

segtree mh, mt;

int root(int n){
    if(par[n] == n) return n;
    else return root(par[n]);
}

set<pair<int,int>> S;
void unite(int u, int v){
    u = root(u);
    v = root(v);
    if (u == v) return;
    ch[u].pb(v);
    S.erase({mn[u], u});
    S.erase({mn[v], v});
    par[v] = u;
    mn[u] = min(mn[u], mn[v]);
    S.insert({mn[u], u});
}

vector<int> t, h;

void rem(int u, int k){
    vector<int> f;
    f.pb(u);
    for (int i = 0; i < f.size(); i++) {
        for (auto j : ch[f[i]]) {
            if (!done[j]) f.pb(j);
        }
    }
    for (auto i : f) {
        done[i] = 1;
        rec[i] = min(rec[i], k);
    }
}

void initialize(vector<int> T, vector<int> H){
    t = T;
    h = H;
    int n = t.size(), m = h.size();
    mh.build(h);
    mt.build(t);

    vector<pair<int,int>> vls;
    for (int i = 0; i < m; i++) {
        rec[i] = n - 1;
        dead[i] = 1;
        vls.pb({h[i], i});
        par[i] = i;
        mn[i] = h[i];
        ch[i] = {};
    }
    sort(vls.rbegin(), vls.rend());

    for (int i = 0; i < n; i++) {
        while (!vls.empty() and t[i] > vls.back().fs) {
            int ind = vls.back().sc;
            vls.pop_back();
            dead[ind] = 0;
            S.insert({mn[ind], ind});
            if (ind + 1 < m and !dead[ind + 1]) unite(ind, ind + 1);
            if (ind - 1 >= 0 and !dead[ind - 1]) unite(ind, ind - 1);
        }
        while (!S.empty() and (*rbegin(S)).fs >= t[i]) {
            int z = (*rbegin(S)).sc;
            rem(z, i - 1);
            S.erase(*rbegin(S));
        }
    }
}

bool can_reach(int L, int R, int S, int D){
    if (D < S) swap(D, S);
    int z = mh.get(S, D);
    int h = min(rec[S], rec[D]);
    int g = mt.get(0, h);
    if (g > z) return 1;
    return false;
}

• 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