Submission #1253021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253021		Sorting	Obstacles for a Llama (IOI25_obstacles)	C++20	21 / 100	2095 ms	8556 KiB

obstacles

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <iomanip>
#include <queue>
#include <stack>
#include <numeric>
#include <cassert>
#include <cmath>
#include <random>
#include <ctime>
#include <chrono>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
// #define sz(x) ((int)x.size())
#define rep(i, a, b) for(int i = a; i < b; ++i)

template<typename C> struct rge{C l, r;};
template<typename C> rge<C> range(C i, C j) { return rge<C>{i, j}; }
template<typename C> ostream& operator<<(ostream &os, rge<C> r) { os << '{'; for(auto it = r.l; it != r.r; it++) os << "," + (it == r.l) << *it; os << '}'; return os; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '{' << p.first << "," << p.second << '}'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ","; return os << '}'; }
void dbg_out() { cerr << ']' << endl; }
template<typename A> void dbg_out(A H) { cerr << H; dbg_out(); }
template<typename A, typename B, typename... C> void dbg_out(A H, B G, C... T) { cerr << H << ","; dbg_out(G, T...); }
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = [", dbg_out(__VA_ARGS__)
#else
#define debug(...)
#endif

template <typename T>
void remove_duplicates(vector<T> &v){
    sort(all(v));
    v.resize(unique(all(v)) - v.begin());
}

template <typename T> void chmin(T &a, T b){ a = (b < a) ? b : a; }
template <typename T> void chmax(T &a, T b){ a = (b > a) ? b : a; } 

int n, m;
vi t, h;

const int N = 2e5 + 3;
const int INF = 1e9;

struct SegmentTree {
    vector<int> mn;
    int sz;

    SegmentTree(int sz): sz(sz) {
        mn.resize(4 * sz);
    }

    void update(int idx, int val, int i, int l, int r) {
        if (r < idx || idx < l) {
            return;
        }
        if (l == r) {
            mn[i] = val;
            return;
        }

        int mid = (l + r) >> 1;
        update(idx, val, 2 * i + 1, l, mid);
        update(idx, val, 2 * i + 2, mid + 1, r);
        mn[i] = min(mn[2 * i + 1], mn[2 * i + 2]);
    }

    int query(int sl, int sr, int i, int l, int r) {
        if (r < sl || sr < l) {
            return INF;
        }
        if (sl <= l && r <= sr) {
            return mn[i];
        }

        int mid = (l + r) >> 1;
        return min(query(sl, sr, 2 * i + 1, l, mid), query(sl, sr, 2 * i + 2, mid + 1, r));
    }

    int query(int sl, int sr) {
        return query(sl, sr, 0, 0, sz - 1);
    }

    void update(int idx, int val) {
        return update(idx, val, 0, 0, sz - 1);
    }
} min_st_h(0);

int min_in_range(int l, int r) {
    return min_st_h.query(l, r);
}

int expand_right(int r, int t_val) {
    while (r < m - 1 && h[r + 1] < t_val) {
        ++r;
    }
    return r;
}

int expand_left(int l, int t_val) {
    while (l > 0 && h[l - 1] < t_val) {
        --l;
    } 
    return l;
}

bool intersect(pii r1, pii r2) {
    return max(r1.first, r2.first) <= min(r2.second, r1.second);
}

bool can_reach(int l, int r, int s, int d) {
    if (s > d) {
        swap(s, d);
    }

    // t[i] > s[j] -> free => t[i] - s[j] > 0

    // 1. Find first biggest on the row in order to form the starting range
    // 2. For each new row, either check if the min of the range is OK or check if you can expand the range
    // 3. How to expand the range? check for larger numbers than t and expand to there.
    // => Need first bigger than query

    pair<int, int> ranges[2]{{s, s},{d, d}};
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 2; ++j) {
            if (min_in_range(ranges[j].first, ranges[j].second) >= t[i]) {
                return false;
            }
            ranges[j].first = expand_left(ranges[j].first, t[i]);
            ranges[j].second = expand_right(ranges[j].second, t[i]);
        }

        if (intersect(ranges[0], ranges[1])) {
            return true;
        }
    }

    return false;
}

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

    min_st_h = SegmentTree(m);
    for (int i = 0; i < m; ++i) {
        min_st_h.update(i, h[i]);
    }
}

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