Submission #1293798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293798		aren_dance	Obstacles for a Llama (IOI25_obstacles)	C++17	0 / 100	53 ms	7360 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_max[N];
int am[N];
void initialize(vector<int> t, vector<int> h) {
    int n=t.size();
    int m=h.size();
    for(int i=1;i<=n;++i){
        mast[i]=t[i-1];
        if(t[pref_maxv[i]]<t[i]){
            pref_maxv[i]=i;
        }
        pref_max[i]=max(pref_max[i-1],t[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_max[mid]>h[i]){
                l=mid+1;
                am[i]=pref_maxv[mid];
            }
            else{
                r=mid-1;
            }
        }
    }
}
int ind(int v){
    int g=am[v];
    for(int i=v+1;i<=m;++i){
        if(mast[g]<=mash[i]){
            break;
        }
        g=am[i];
    }
    int e=am[v];
    for(int i=v-1;i>0;--i){
        if(mast[g]<=mash[i]){
            break;
        }
        g=am[i];
    }
    return max(g,e);
}
bool can_reach(int l, int r, int s, int d) {
	int u=ind(s+1);
    int g=ind(d+1);
    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