| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1254868 | PenguinsAreCute | Obstacles for a Llama (IOI25_obstacles) | C++20 | 0 ms | 0 KiB |
#include "obstacles_ioi25.h"
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(69);
struct seg {
int n;
vector<int> v;
seg(int _n): n(_n), v(2*_n,-1e9-5) {}
void up(int x, int u) {
for(x+=n;x;x>>=1)
v[x]=max(v[x],u);
}
int qry(int l, int r) {
int ans = -1e9-5;
for(l+=n,r+=n+1;l<r;l>>=1,r>>=1) {
if(l&1)
ans=max(ans,v[l++]);
if(r&1)
ans=max(ans,v[--r]);
}
return ans;
}
};
seg lft(0), rgt(0);
vector<unsigned long long> cc;
void initialize(std::vector<int> T, std::vector<int> H) {
int N = T.size(), M = H.size();
/*
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++)
cerr<<(T[i]>H[j]?'.':'#');
cerr<<"\n";
}
*/
lft = seg(M);
rgt = seg(M);
seg minH(M);
for(int i=0;i<M;i++)
minH.up(i,-H[i]);
cc.resize(M,0);
cc[0] = 0;
vector<int> maxT(N+1), minT(N+1);
maxT[0] = 0;
minT[0] = 1e9 + 7;
for(int i=0;i<N;i++) {
maxT[i+1] = max(maxT[i],T[i]);
minT[i+1] = min(minT[i],T[i]);
}
// L shape covering left
vector<int> mono;
for(int i=0;i<M;i++) {
while(mono.size() && H[mono.back()] >= H[i])
mono.pop_back();
mono.push_back(i);
int pos = upper_bound(maxT.begin(),maxT.end(),H[i]) - maxT.begin() - 1;
if(!pos)
continue;
if(pos == N)
lft.up(i,1);
int curTemp = minT[pos];
auto it = partition_point(mono.begin(),mono.end(),[&H,curTemp](int x) {
return H[x] < curTemp;
});
int L = (it==mono.begin()?-1:*--it);
lft.up(i,-L);
}
// L shape covering right
mono.clear();
for(int i=M;i--;) {
while(mono.size() && H[mono.back()] >= H[i])
mono.pop_back();
mono.push_back(i);
int pos = upper_bound(maxT.begin(),maxT.end(),H[i]) - maxT.begin() - 1;
if(!pos)
continue;
if(pos == N)
rgt.up(i,N);
int curTemp = minT[pos];
auto it = partition_point(mono.begin(),mono.end(),[&H,curTemp](int x) {
return H[x] < curTemp;
});
int R = (it==mono.begin()?M:*--it);
rgt.up(i,R);
}
// boxed in
vector<pair<int,int>> sortH(M);
for(int i=0;i<M;i++)
sortH[i] = {H[i], i};
sort(sortH.begin(),sortH.end(),greater<pair<int,int>>());
set<int> seen;
for(auto [h, i]: sortH) {
auto it = seen.insert(i).first;
int pos = upper_bound(maxT.begin(),maxT.end(),H[i]) - maxT.begin() - 1;
if(!pos)
continue;
int curTemp = minT[pos];
if(it != seen.begin() && curTemp <= -minH.qry(*prev(it),*it)) {
unsigned long long cur = rng();
cc[*prev(it)] += cur;
cc[*it] -= cur;
}
if(next(it) != seen.end() && curTemp <= -minH.qry(*it,*next(it))) {
unsigned long long cur = rng();
cc[*next(it)] += cur;
cc[*it] -= cur;
}
}
for(int i=1;i<M;i++)
cc[i] += cc[i-1];
}
bool can_reach(int L, int R, int S, int D) {
if(S > D)
swap(S, D);
return L <= -lft.qry(S,D) && R >= rgt.qry(S,D) && cc[S] == cc[D];
}