Submission #1257267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257267		yhx3	Obstacles for a Llama (IOI25_obstacles)	C++20	0 / 100	87 ms	8636 KiB

obstacles

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ord_set tree < int ,  null_type ,  less ,  rb_tree_tag ,  tree_order_statistics_node_update>
#define ll unsigned long long
#define rep(i,a,b) for (int i = a; i < b; i++)
#define rrep(i,a,b) for (int i = a; i >= b; i--)
void N() {cout<<"NO\n";}
void Y() {cout<<"YES\n";}
void isTrue(bool ope) {
    if (ope) Y();else N();
}
int MD = 1e9+7;
ll MX_VL = 1e18;
int MX_ll = 2e9;

vector<int> T;
vector<int> H;
vector<int> pref;
vector<int> pref2;
vector<int> pnt;
vector<int> cnc2;
int m;
int n;

void initialize(std::vector<int> Tp, std::vector<int> Hp) {
    T = Tp;
    H = Hp;
    m = Hp.size();
    n = Tp.size();
    pref.resize(m,0);
    pref2.resize(m,0);
    pref2[0] = H[0] >= 2;
    pref[0] = Tp.back() <= Hp[0];
    rep(i,0,m) {
        if (H[i] == 0) pnt.push_back(i);
        if (H[i] >= 2) {
            cnc2.push_back(i);
            pref2[i] = pref2[i-1]+1;
        } else pref2[i] = pref2[i-1];
    }
    rep(i,1,m) {
        pref[i] = (Tp.back() <= Hp[i]) + pref[i-1];
    }
}

bool can_reach(int L, int R, int S, int D) {
    auto tt = lower_bound(cnc2.begin(),cnc2.end(),S);
    if (tt == cnc2.end() || *tt > D) return true;
    int i1 = lower_bound(cnc2.begin(),cnc2.end(),D)-cnc2.begin();
    int l = i1-1 >= 0 ? cnc2[i1-1]+1 : 0;
    int r = i1 < cnc2.size() ? cnc2[i1]-1 : m-1;
    if (pref[D]!=pref[S]) return false;
    auto it = lower_bound(pnt.begin(),pnt.end(),l);
    if (it == pnt.end() || *it > r) return false;
    auto it2 = lower_bound(pnt.begin(),pnt.end(),S);
    if (it2 != pnt.end() && *it2 < *tt && pref[(*it)]==pref[S]) {
        return true;
    }
    int cs = upper_bound(pnt.begin(),pnt.end(),S)-pnt.begin()-1;
    int x =  lower_bound(cnc2.begin(),cnc2.end(),S) - cnc2.begin() - 1;
    int prev = x >= 0 ? cnc2[x] : -1;
    if (cs >= 0 && pnt[cs] > prev && pref[S] == pref[pnt[cs]]) return true;
    return false;
}

• 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