Submission #1261607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261607		alexdd	Obstacles for a Llama (IOI25_obstacles)	C++20	0 / 100	2096 ms	8632 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> t,h;
int maxl[200005];
int maxpref[200005];
void initialize(std::vector<int> T, std::vector<int> H)
{
    t = T;
    h = H;
    maxpref[0] = t[0];
    for(int i=1;i<t.size();i++)
        maxpref[i] = max(maxpref[i-1], t[i]);

    priority_queue<pair<int,int>> pq;
    for(int i=0;i<h.size();i++)
    {
        maxl[i] = 0;
        while(maxl[i] + 1 < t.size() && t[maxl[i]+1] > h[i])
            maxl[i]++;
        pq.push({maxl[i], i});
    }
    while(!pq.empty())
    {
        auto [cval,i] = pq.top();
        pq.pop();
        if(maxl[i] != cval)
            continue;
        for(int v:{i-1,i+1})
        {
            if(0 <= v && v < h.size() && maxl[v] < maxl[i] && h[v] < t[maxpref[maxl[i]]])
            {
                maxl[v] = maxl[i];
                pq.push({maxl[v], v});
            }
        }
    }
}

bool can_reach(int L, int R, int S, int D)
{
    int maxh = 0;
    for(int i=L;i<=R;i++)
        maxh = max(maxh, h[i]);
    return (maxpref[maxl[L]] >= maxh && maxpref[maxl[R]] >= maxh);
}

• 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