Submission #1253992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253992		countless	Obstacles for a Llama (IOI25_obstacles)	C++20	44 / 100	2095 ms	11336 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O5")

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

const int INF = 1e9+5;

struct maxtree {
    int n, sz;
    vector<int> tree;

    maxtree(int l, int r, vector<int> &a) {
        n = r+1;
        sz = 2*n;
        tree.resize(sz);

        for (int i = 0; i < n; i++) {
            tree[i + n] = a[i];
        }

        for (int i = n-1; i > 0; i--) {
            tree[i] = max(tree[i<<1], tree[i<<1|1]);
        }
    }

    int query(int l, int r) {
        if (l == r) return tree[l + n];
        l += n, r += n;
        int res = -1;
        while (l <= r) {
            if (l & 1) {
                res = max(res, tree[l]);
                l++;
            }

            if (!(r & 1)) {
                res = max(res, tree[r]);
                r--;
            }

            l >>= 1, r >>= 1;
        }
        return res;
    }
};

struct mintree {
    int n, sz;
    vector<int> tree;

    mintree(int l, int r, vector<int> &a) {
        n = r+1;
        sz = 2*n;
        tree.resize(sz);
        
        for (int i = 0; i < n; i++) {
            tree[i + n] = a[i];
        }

        for (int i = n-1; i > 0; i--) {
            tree[i] = min(tree[i<<1], tree[i<<1|1]);
        }
    }

    int query(int l, int r) {
        if (l == r) return tree[l + n];
        l += n, r += n;
        int res = INF;
        while (l <= r) {
            if (l & 1) {
                res = min(res, tree[l]);
                l++;
            }

            if (!(r & 1)) {
                res = min(res, tree[r]);
                r--;
            }

            l >>= 1, r >>= 1;
        }
        return res;
    }
};

int N, M;
vector<int> T, H;
maxtree *mxt;
mintree *mnt;

void initialize(vector<int> _T, vector<int> _H) {
    N = _T.size(), M = _H.size();
    T = _T, H = _H;
    mxt = new maxtree(0, M-1, H);
    mnt = new mintree(0, M-1, H);
    return;
}

int cnt = 0;
int can_reach(int fir, int lo, int hi, int S, int D) {
    {
        int l = S, r = D;
        while (r - l > 1) {
            int m = (l+r) / 2;
            if (fir > mxt->query(S, m)) {
                l = m;
            } else {
                r = m;
            }
        }

        S = l;
    }

    {
        int l = S, r = D;
        while (r - l > 1) {
            int m = (l+r) / 2;
            if (fir > mxt->query(m, D)) {
                r = m;
            } else {
                l = m;
            }
        }

        D = r;
    }

    int right = -1, left = M;
    {
        int l = -1, r = S+1;
        while (r - l > 1) {
            int m = (l+r) / 2;
            if (lo > mnt->query(m, S)) {
                l = m;
            } else {
                r = m;
            }
        }

        right = l;
        if (!(lo > mnt->query(right, S))) right = -1;
    }

    {
        int l = D-1, r = M;
        while (r - l > 1) {
            int m = (l+r) / 2;
            if (lo > mnt->query(D, m)) {
                r = m;
            } else {
                l = m;
            }
        }

        left = r;
        if (!(lo > mnt->query(D, left))) left = M;
    }

    if (right == -1 or left == M) return 0;
    if (!(fir > mxt->query(right, S))) return 0;
    if (!(fir > mxt->query(D, left))) return 0;

    if (mxt->query(right, left) < hi) return 1;
    else return 2;
}

bool can_reach(int L, int R, int S, int D) {
    cnt++;
    if (S > D) swap(S, D);
    
    int mx = mxt->query(S, D);
    if (T[0] > mx) return true;
    
    mx = T[0];
    int mn = T[0];
    for (int i = 1; i < N; i++) {
        mn = min(mn, T[i]);
        if (T[i] < mx) continue;
        int res = can_reach(mx, mn, T[i], S, D);
        if (res == 0) {

        } else if (res == 1) {
            return true;
        } else if (res == 2) {
            mx = max(mx, T[i]);
        }
    }

    return false;
}

// subtask 3 3Q log N log M
// subtask 4 10N log N log M
// subtask 5 2d?! or binary search for the thing we need first

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