Submission #1311973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311973		garam1732	Obstacles for a Llama (IOI25_obstacles)	C++20	0 / 100	215 ms	85972 KiB

obstacles

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

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) (lower_bound(all(v), (x))-(v).begin())
#define ubd(v,x) (upper_bound(all(v), (x))-(v).begin())
#define sz(v) ((int)(v).size())

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 100100*2;
const ll MOD = 998244353;
const ll INF = 1e18;

int sp[20][MAXN];
int rmq(int a, int b) {
    int h = (int)floor(log2(b-a+1));
    return min(sp[h][a], sp[h][b-(1<<h)+1]);
}

vector<pi> row;
vector<int> lpar, rpar;

set<pi> s1, s2;

pi node[MAXN]; int ncnt;
pi info[MAXN];
map<pi, int> mp;

int num[MAXN];
int grp[MAXN], gcnt;

int root(int x, vector<int>& par) {
    return par[x]==x?x:par[x]=root(par[x], par);
}

struct Parent {
    int par, lcol, rcol;
} pnt[20][MAXN];

void update(int x, int p, int val) {
    pnt[0][x].par = p;
    auto [a,b] = node[x];
    
    int lb=a,ub=b,mid; while(lb<ub) {
        mid=lb+ub>>1;
        if(rmq(mid+1,ub) < val) lb=mid+1;
        else ub=mid;
    } pnt[0][x].rcol = lb;

    lb=a,ub=b,mid; while(lb<ub) {
        mid=lb+ub>>1;
        if(rmq(lb,mid) < val) ub=mid;
        else lb=mid+1;
    } pnt[0][x].lcol = lb;
}

int dep[MAXN];
vector<int> adj[MAXN];
void dfs(int here) {
    grp[here] = gcnt;
    for(int there:adj[here]) {
        dep[there] = dep[here]+1;
        dfs(there);
    }
}
pi lca(pi a, pi b) {
    int r=MAXN, l=-1;
    if(dep[a.ff]>dep[b.ff]) swap(a,b);
    for(int j=19;j>=0;j--) if(dep[a.ff] <= dep[pnt[j][b.ff].par]) {
        if(b.ss==0) r=min(r, pnt[j][b.ff].rcol);
        else l=max(l, pnt[j][b.ff].lcol);
        b.ff = pnt[j][b.ff].par;
    }

    if(a.ff==b.ff) return {r,l};

    for(int j=19;j>=0;j--) if(pnt[j][a.ff].par^pnt[j][b.ff].par) {
        if(a.ss==0) r=min(r, pnt[j][a.ff].rcol);
        else l=max(l, pnt[j][a.ff].lcol);
        a.ff = pnt[j][a.ff].par;

        if(b.ss==0) r=min(r, pnt[j][b.ff].rcol);
        else l=max(l, pnt[j][b.ff].lcol);
        b.ff = pnt[j][b.ff].par;
    }

    if(a.ss==0) r=min(r, pnt[0][a.ff].rcol);
    else l=max(l, pnt[0][a.ff].lcol);

    if(b.ss==0) r=min(r, pnt[0][b.ff].rcol);
    else l=max(l, pnt[0][b.ff].lcol);
    return {r,l};
}

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

    for(int i=0;i<m;i++) sp[0][i] = H[i];
    for(int j=1;j<20;j++) for(int i=0;i<m;i++) {
        sp[j][i] = sp[j-1][i];
        if(i+(1<<(j-1)) < m) sp[j][i] = min(sp[j][i], sp[j-1][i+(1<<(j-1))]);
    }

    row.push_back({0,0});
    for(int i=1;i<n;i++) {
        if(T[row.back().ff] < T[i]) 
            row.push_back({i,0});
    }

    for(int i=1;i<sz(row);i++) {
        int mn = INT_MAX;
        for(int j=row[i-1].ff+1;j<row[i].ff;j++) {
            mn = min(mn, T[j]);
        } row[i].ss = mn;
    }

    lpar.resize(m); rpar.resize(m);
    for(int i=0;i<m;i++) lpar[i]=rpar[i]=i;
    int idx=0;
    while(idx<m) {
        while(idx<m && H[idx]>=T[0]) idx++;
        if(idx==m) break;

        int nx=idx;
        while(nx<m && H[nx]<T[0]) nx++;

        rpar[idx] = nx-1; lpar[nx-1] = idx;

        node[ncnt] = {idx,nx-1};
        mp[node[ncnt]] = ncnt;

        int mn=rmq(idx, nx-1);
        s1.insert({mn, ncnt});
        info[ncnt].ff = mn;

        mn = INT_MAX;
        if(idx-1>=0) mn=min(mn,H[idx-1]);
        if(nx<m) mn=min(mn, H[nx]);
        s2.insert({mn, ncnt});
        info[ncnt].ss = mn;

        pnt[0][ncnt] = {0, idx, nx-1};

        for(int i=idx;i<nx;i++) num[i] = ncnt;
        idx = nx; ncnt++;
    }

    auto clean = [&] (int x) {
        s1.erase({info[x].ff, x}); s2.erase({info[x].ss, x}); mp.erase(node[x]);
    };
    for(int i=1;i<sz(row);i++) {
        while(s1.size() && s1.rbegin()->ff >= row[i].ss) {
            auto x = s1.rbegin()->ss;
            clean(x);
        }

        while(s2.size() && s2.begin()->ff < T[row[i].ff]) {
            auto x = s2.begin()->ss; auto [a,b] = node[x];
            clean(x);

            vector<int> w = {x};
            while(a-1>=0) {
                if(H[a-1] >= T[row[i].ff]) break;

                int a1 = root(a-1, lpar);
                if(mp.find({a1,a-1}) != mp.end()) {
                    w.push_back(mp[{a1,a-1}]);
                    clean(mp[{a1,a-1}]);
                }
                a = a1;
            } while(b+1<m) {
                if(H[b+1] >= T[row[i].ff]) break;

                int b1 = root(b+1, rpar);
                if(mp.find({b+1,b1}) != mp.end()) {
                    w.push_back(mp[{b+1,b1}]);
                    clean(mp[{b+1,b1}]);
                }
                b = b1;
            }//for(int x:w)cout<<x<<bl;cout<<endl;

            rpar[a] = b; lpar[b] = a; node[ncnt] = {a,b}; mp[node[ncnt]] = ncnt;
            info[ncnt] = {rmq(a,b), min((a-1>=0?H[a-1]:INT_MAX), (b+1<m?H[b+1]:INT_MAX))};
            s1.insert({info[ncnt].ff, ncnt}); s2.insert({info[ncnt].ss, ncnt});

            pnt[0][ncnt] = {ncnt, a, b};
            for(int z:w) {
                update(z, ncnt, row[i].ss);
                adj[ncnt].push_back(z);
            } ncnt++;
        }//for(auto x:s2)cout<<x.ff<<bl<<x.ss<<endl;
    }//for(int i=0;i<ncnt;i++) cout<<pnt[0][i].par<<bl<<pnt[0][i].lcol<<bl<<pnt[0][i].rcol<<endl;
    
    for(int j=1;j<20;j++) {
        for(int i=0;i<ncnt;i++) {
            pnt[j][i].par = pnt[j-1][pnt[j-1][i].par].par;
            pnt[j][i].rcol = min(pnt[j-1][i].rcol, pnt[j-1][pnt[j-1][i].par].rcol);
            pnt[j][i].lcol = max(pnt[j-1][i].lcol, pnt[j-1][pnt[j-1][i].par].lcol);
        }
    } for(int i=0;i<ncnt;i++) if(pnt[0][i].par==i) {
        gcnt++; dfs(i);
    }
}

bool can_reach(int L, int R, int S, int D) {
    int x=num[S], y=num[D];
    if(grp[x]^grp[y]) return 0;

    auto [a,b] = lca({x,0},{y,1});
    return (L<=a && b<=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