Submission #1255637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255637		otarius	Obstacles for a Llama (IOI25_obstacles)	C++20	83 / 100	100 ms	27940 KiB

obstacles

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

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngl(chrono::steady_clock::now().time_since_epoch().count());

// #define int long long
// #define int unsigned long long

// #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
// #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>

// const ll mod = 1e9 + 7;
// const ll mod = 998244353;

const ll inf = 1e9;
const ll biginf = 1e18;
const int maxN = 2 * 1e5 + 15;

int n, m, mx[maxN], mn[maxN], lft[maxN], rgt[maxN], st[maxN][20], lg[maxN], par[maxN], sz[maxN];
int query(int l, int r) {
    if (r < l) return 0;
    int z = lg[r - l + 1];
    return max(st[l][z], st[r - (1 << z) + 1][z]);
}

void make_set() {
    for (int i = 1; i <= m; i++) {
        par[i] = i; sz[i] = 1;
    }
}
int find_set(int x) {
    if (par[x] == x)
        return x;
    return par[x] = find_set(par[x]);
}
void union_set(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    par[b] = a; sz[a] += sz[b];
}

void initialize(vector<int> t, vector<int> h) {
    n = t.size(); m = h.size();
    t.insert(t.begin(), 0);
    h.insert(h.begin(), 0);


    mx[0] = -inf; mn[0] = inf;
    for (int i = 1; i <= n; i++) {
        mx[i] = max(mx[i - 1], t[i]);
        mn[i] = min(mn[i - 1], t[i]);
    }

    stack<int> s;
    for (int i = 1; i <= m; i++) {
        while (!s.empty() && h[s.top()] >= h[i]) {
            rgt[s.top()] = i; s.pop();
        } s.push(i);
    } while (!s.empty()) rgt[s.top()] = m + 1, s.pop();

    for (int i = m; i >= 1; i--) {
        while (!s.empty() && h[s.top()] >= h[i]) {
            lft[s.top()] = i; s.pop();
        } s.push(i);
    } while (!s.empty()) lft[s.top()] = 0, s.pop();

    for (int i = 2; i <= m; i++)
        lg[i] = lg[i / 2] + 1;
    for (int i = 1; i <= m; i++)
        st[i][0] = h[i];
    for (int j = 1; j < 20; j++)
        for (int i = 1; i + (1 << j) - 1 <= m; i++)
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    make_set();

    for (int i = 1; i <= m; i++) {
        if (mn[1] <= h[i]) continue;

        int l = 1, r = n, mid, ans;
        while (l <= r) {
            mid = (l + r) / 2;
            if (mn[mid] > h[i]) {
                ans = mid; l = mid + 1;
            } else r = mid - 1;
        }

        if (lft[i] != 0 && mx[ans] > query(lft[i], i)) union_set(lft[i], i);
        if (rgt[i] != m + 1 && mx[ans] > query(i, rgt[i])) union_set(i, rgt[i]);
    }
}

bool can_reach(int L, int R, int S, int D) {
    return (find_set(S + 1) == find_set(D + 1));
}

// int main() {
//   int N, M;
//   assert(2 == scanf("%d %d", &N, &M));
//   std::vector<int> T(N), H(M);
//   for (int i = 0; i < N; i++)
//     assert(1 == scanf("%d", &T[i]));
//   for (int i = 0; i < M; i++)
//     assert(1 == scanf("%d", &H[i]));

//   int Q;
//   assert(1 == scanf("%d", &Q));
//   std::vector<int> L(Q), R(Q), S(Q), D(Q);
//   for (int i = 0; i < Q; i++)
//     assert(4 == scanf("%d %d %d %d", &L[i], &R[i], &S[i], &D[i]));

//   fclose(stdin);

//   std::vector<bool> A(Q);

//   initialize(T, H);

//   for (int i = 0; i < Q; i++)
//     A[i] = can_reach(L[i], R[i], S[i], D[i]);

//   for (int i = 0; i < Q; i++)
//     if (A[i])
//       printf("1\n");
//     else
//       printf("0\n");
//   fclose(stdout);

//   return 0;
// }

• 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