제출 #1251758

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251758		Zbyszek99	장애물 (IOI25_obstacles)	C++20	58 / 100	1960 ms	142276 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9;

struct table
{
    pii min_[200001][18];
    pii max_[200001][18];
    void set(vi v)
    {
        rep(i,siz(v))
        {
            min_[i][0] = {v[i],i};
            max_[i][0] = {v[i],i};
        }
        rep2(bit,1,17)
        {
            rep(i,siz(v))
            {
                min_[i][bit] = min(min_[i][bit-1],(i+(1<<(bit-1)) < siz(v) ? min_[i+(1<<(bit-1))][bit-1] : (pii){1e9,1e9}));
                max_[i][bit] = max(max_[i][bit-1],(i+(1<<(bit-1)) < siz(v) ? max_[i+(1<<(bit-1))][bit-1] : (pii){-1e9,-1e9}));
            }
        }
    }
    pii get_max(int l, int r)
    {
        int lg = __lg(r-l+1);
        return max(max_[l][lg],max_[r-(1 << lg)+1][lg]);
    }
    pii get_min(int l, int r)
    {
        int lg = __lg(r-l+1);
        return min(min_[l][lg],min_[r-(1 << lg)+1][lg]);
    }
};

table tableX;
table tableY;
int max_H[200001];
int X[200001];
int Y[200001];
vi pref;

void split(int l, int r, int h, vector<pii>& ans)
{
    if(l > r) return;
    int max_col = tableX.get_max(l,r).ss;
    if(Y[h] > X[max_col]) ans.pb({l,r});
    else
    {
        split(l,max_col-1,h,ans);
        split(max_col+1,r,h,ans);
    }
}

void rek(int l, int r, int pref_max, int pop)
{
    cerr << l << " " << r << " " << pref_max << " " << pop << " rek\n";
    int max_col = tableX.get_max(l,r).ss;
    int l2 = 0;
    int r2 = pref_max;
    int down_ok = pref_max;
    while(l2 <= r2)
    {
        int mid = (l2+r2)/2;
        if(Y[pref[mid]] > X[max_col])
        {
            down_ok = mid;
            r2 = mid-1;
        }
        else
        {
            l2 = mid+1;
        }
    }
    cerr << down_ok << " ok\n";
    vector<pii> segs;
    if(down_ok != 0) split(l,r,pref[down_ok-1],segs);
    else segs.pb({l,r});
    int pop2 = pop;
    if(down_ok != pref_max)
    {   
        int l2 = down_ok;
        int r2 = pref_max;
        int up = down_ok;
        int min_col = tableX.get_min(l,r).ss;
        while(l2 <= r2)
        {
            int mid = (l2+r2)/2;
            if(tableY.get_min(pref[down_ok],pref[mid]).ff > X[min_col])
            {
                up = mid;
                l2 = mid+1;
            }
            else
            {
                r2 = mid-1;
            }
        }
        cerr << up << " up\n";
        if(up != pref_max)
        {
            pop2 = pref[up];
        }
    }
    if(down_ok == 0)
    {
        rep2(i,l,r)
        {
            max_H[i] = pop2;
        }
        return;
    }
    forall(it,segs)
    {
        if(tableY.get_min(pref[down_ok-1],pref[down_ok]).ff > tableX.get_min(it.ff,it.ss).ff)
        {
            rek(it.ff,it.ss,down_ok-1,pop2);
        }
        else
        {
            rek(it.ff,it.ss,down_ok-1,down_ok-1);
        }
    }
}

void initialize(vi T, vi H) 
{
    T.pb(-1);
    rep(i,siz(T)) Y[i] = T[i];
    rep(i,siz(H)) X[i] = H[i];
    tableY.set(T);
    tableX.set(H);
    int pop = -1;
    rep(i,siz(T))
    {
        if(Y[i] >= pop)
        {
            pref.pb(i);
            pop = Y[i];
        }
    }
    rek(0,siz(H)-1,siz(pref)-1,pref.back());
}

bool can_reach(int L, int R, int S, int D) 
{
    int row = min(max_H[S],max_H[D]);
    if(D > S) swap(D,S);
    return tableX.get_max(D,S).ff < Y[row];
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 21 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17