Submission #1253994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253994		countless	Obstacles for a Llama (IOI25_obstacles)	C++20	24 / 100	189 ms	27072 KiB

obstacles

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

typedef long long ll;
typedef long double ld;

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

const int INF = 1e9+5;

// consider changing to array based if needed
struct segtree {
    int l, r;
    int val;
    segtree *left, *right;

    void merge() {
        val = max(left->val, right->val);
    }

    segtree(int l, int r, vector<int> &a) : l(l), r(r) {
        if (l == r) {
            val = a[l];
            return;
        }

        int m = (l+r) / 2;
        left = new segtree(l, m, a);
        right = new segtree(m+1, r, a);
        merge();
    }

    int query(int ql, int qr) {
        if (ql > r or qr < l) return -1;
        if (ql <= l and r <= qr) return val;

        return max(left->query(ql, qr), right->query(ql, qr));
    }
};

int N, M, BEST;
vector<int> T, H;
segtree *st;

void initialize(vector<int> _T, vector<int> _H) {
    N = _T.size(), M = _H.size();
    T = _T, H = _H;
    st = new segtree(0, M-1, H);
    BEST = *max_element(T.begin(), T.end());
    return;
}

bool can_reach(int L, int R, int S, int D) {
    if (S > D) swap(S, D);
    int mx = st->query(S, D);
    // cerr << T[0] sp mx << endl;
    return BEST > mx;
}

// imported from qoj

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