| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1251459 | KasymK | 장애물 (IOI25_obstacles) | C++20 | 0 ms | 0 KiB |
#include "bits/stdc++.h"
// #include "grader.cpp"
#include "obstacles-online.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N = 2e5+5;
int par[N][2];
vector<int> A;
void initialize(vector<int> t, vector<int> h){
assert(A.empty());
int m=(int)h.size();
for(int i = 1; i <= m; ++i){
for(int ad = 0; ad < 2; ++ad)
par[i][ad]=par[i-1][ad];
if(h[i-1]<2)
par[i][0]++;
if(h[i-1]<3)
par[i][1]++;
if(h[i-1]==0)
A.pb(i);
}
return;
}
bool can_reach(int l, int r, int s, int d){
if(s>d)
swap(s, d);
s++, d++;
if(s==d)
return 1;
if(par[d][0]-par[s-1][0]==d-s+1)
return 1;
if(par[d][1]-par[s-1][1]!=d-s+1)
return 0;
if(A.empty())
return 0;
auto ee=lower_bound(all(A), s);
if(ee!=A.end()){
int j=*ee;
if(j<d and par[j][0]-par[s-1][0]==j-s+1){
auto oo=upper_bound(all(A), d);
if(oo!=A.end()){
int jj=*oo;
if(par[jj][0]-par[d-1][0]==jj-d+1 and par[jj][1]-par[j-1][1]==jj-j+1)
return 1;
}
oo--;
int jj=*oo;
assert(jj>=j);
if(par[d][0]-par[jj-1][0]==d-jj+1)
return 1;
}
}
ee--;
int j=*ee;
if(par[s][0]-par[j-1][0]==s-j+1){
auto oo=upper_bound(all(A), d);
if(oo!=A.end()){
int jj=*oo;
if(par[jj][1]-par[j-1][1]==jj-j+1 and par[jj][0]-par[d-1][0]==jj-d+1)
return 1;
}
if(oo!=A.begin()){
oo--;
int jj=*oo;
if(jj!=j){
if(par[jj][1]-par[j-1][1]==jj-j+1 and par[d][0]-par[jj-1][0]==d-jj+1)
return 1;
}
}
}
return 0;
}