Submission #1261619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261619		alexdd	Obstacles for a Llama (IOI25_obstacles)	C++20	10 / 100	2094 ms	13780 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> t,h;
int aint[800005];
void build(int nod, int st, int dr)
{
    if(st == dr)
    {
        aint[nod] = h[st];
        return;
    }
    int mij = (st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    aint[nod] = max(aint[nod*2], aint[nod*2+1]);
}
int qry(int nod, int st, int dr, int le, int ri)
{
    if(le > ri)
        return -1;
    if(le == st && dr == ri)
        return aint[nod];
    int mij = (st+dr)/2;
    return max(qry(nod*2,st,mij,le,min(mij,ri)), qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
}
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]);
    build(1,0,(int)h.size()-1);
    priority_queue<pair<int,int>> pq;
    for(int i=0;i<h.size();i++)
    {
        maxl[i] = 0;
        while(maxl[i] + 1 < (int)t.size() && t[maxl[i]+1] > h[i])
            maxl[i]++;
        maxl[i] = maxpref[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 < (int)h.size() && maxl[v] < maxl[i] && h[v] < maxl[i])
            {
                maxl[v] = maxl[i];
                pq.push({maxl[v], v});
            }
        }
    }
}

bool can_reach(int L, int R, int S, int D)
{
    if(S > D)
        swap(S, D);
    /*int maxh = 0;
    for(int i=S;i<=D;i++)
        maxh = max(maxh, h[i]);*/
    int maxh = qry(1,0,(int)h.size()-1,S,D);
    return (maxl[S] > maxh && maxl[D] > maxh);
}

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