Submission #1293856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293856		aren_dance	Obstacles for a Llama (IOI25_obstacles)	C++17	0 / 100	2096 ms	7356 KiB

obstacles

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+1;
int mast[N];
int mash[N];
int n,m;
int pref_maxv[N];
int pref_min[N];
int am[N];
void initialize(vector<int> t, vector<int> h) {
    int n=t.size();
    int m=h.size();
    pref_min[0]=1e9;
    for(int i=1;i<=n;++i){
        mast[i]=t[i-1];
        if(mast[pref_maxv[i]]<mast[i]){
            pref_maxv[i]=i;
        }
        pref_min[i]=min(pref_min[i-1],mast[i]);
    }
    for(int i=1;i<=m;++i){
        mash[i]=h[i-1];
        int l=1;
        int r=n;
        while(l<=r){
            int mid=(l+r)/2;
            if(pref_min[mid]>mash[i]){
                l=mid+1;
                am[i]=pref_maxv[mid];
            }
            else{
                r=mid-1;
            }
        }
    }
}
int ind(int v){
    int g=am[v];
    int s=v;
    int e=v;
    while(true){
        int f=g;
        for(int i=e+1;i<=m;++i){
            if(mast[g]<=mash[i]){
                break;
            }
            e=i;
            g=max(g,am[i]);
        }
        for(int i=s-1;i>0;--i){
            if(mast[g]<=mash[i]){
                break;
            }
            s=i;
            g=max(g,am[i]);
        }
        if(f==g){
            break;
        }
    }
    return g;
}
bool can_reach(int l, int r, int s, int d) {
    s++;
    d++;
	int u=ind(s);
    int g=ind(d);
    int x=min(u,g);
    for(int i=min(s,d);i<=max(s,d);++i){
        if(mast[x]<=mash[i]){
            return 0;
        }
    }
    return 1;
}

• 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