Submission #1339288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1339288		khanhphucscratch	Obstacles for a Llama (IOI25_obstacles)	C++20	21 / 100	53 ms	5896 KiB

obstacles

#include "obstacles.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> t, h;
void initialize(vector<int> T, vector<int> H) {
    t = T; h = H;
}

bool can_reach(int L, int R, int S, int D) {
    //Subtask 3+4
    if(S > D) swap(S, D);
    int l1 = S, r1 = S, l2 = D, r2 = D;
    int minh1 = h[S], minh2 = h[D];
    for(int i = 0; i < t.size(); i++){
        if(t[i] <= minh1 || t[i] <= minh2) return 0;
        while(l1 >= 1 && h[l1] < t[i]) minh1 = min(minh1, h[l1--]);
        while(r1 < h.size() && h[r1] < t[i]) minh1 = min(minh1, h[r1++]);
        while(l2 >= 1 && h[l2] < t[i]) minh2 = min(minh2, h[l2--]);
        while(r2 < h.size() && h[r2] < t[i]) minh2 = min(minh2, h[r2++]);
        if(r1 >= l2) return 1;
    }
    return 0;

}

• 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