Submission #1251261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251261		bronze_coder	장애물 (IOI25_obstacles)	C++20	83 / 100	212 ms	28480 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> h;
vector<int> parent;

struct DSU{
    vector<int> e;
    vector<int> z;
    DSU(int n){
        for(int i=0;i<n;i++){
            e.push_back(-1);
            z.push_back(i);
        }
    }
    int parent(int i){
        if(e[i]<0){
            return i;
        }
        e[i] = parent(e[i]);
        return e[i];
    }
    bool join(int i,int j){
        int x = parent(i);
        int y = parent(j);
        if(x==y){
            return false;
        }
        if(e[x]<e[y]){
            swap(x,y);
        }
        e[y] += e[x];
        e[x] = y;
        if(h[z[x]]<h[z[y]]){
            z[y] = z[x];
        }
        return true;
    }
};

DSU ans(0);

struct SegmentTree{
    vector<int> l;
    int n;
    SegmentTree(int m){
        n = m;
        for(int i=0;i<2*n;i++){
            l.push_back(0);
        }
    }
    void update(int i,int x){
        i += n;
        l[i] = x;
        while(i>0){
            i /= 2;
            l[i] = min(l[2*i],l[2*i+1]);
        }
    }
    int query(int i,int j){
        i += n;
        j += n;
        int ans = l[i];
        while(i<j){
            if(i&2){
                ans = min(l[i],ans);
                i++;
            }
            if(j&2){
                ans = min(l[j-1],ans);
                j--;
            }
            i /= 2;
            j /= 2;
        }
        return ans;
    }
};

void initialize(vector<int> T, vector<int> H){
    int n = T.size();
    int m = H.size();
    vector<int> t1 = {T[0]};
    vector<pair<int,int>> l;
    for(int i=1;i<n;i++){
        t1.push_back(min(t1[i-1],T[i]));
    }
    for(int i=0;i<m;i++){
        h.push_back(H[i]);
    }

    for(int i=0;i<n;i++){
        l.push_back({T[i],-i-1});
    }
    for(int i=0;i<m;i++){
        l.push_back({H[i],i});
    }

    sort(l.begin(),l.end());
    vector<int> stop(m);
    int cur = n;
    for(int i=0;i<n+m;i++){
        if(l[i].second<0){
            cur = min(cur,-l[i].second-1);
        }
        else{
            stop[l[i].second] = cur;
        }
    }


    vector<pair<int,int>> l1;
    for(int i=0;i<m;i++){
        l1.push_back({stop[i],i});
    }
    for(int i=0;i<n;i++){
        l1.push_back({i,-i-1});
    }
    sort(l1.begin(),l1.end());
    cur = -1;
    vector<int> start(m);
    for(int i=0;i<n+m;i++){
        if(l1[i].second<0){
            cur = max(cur,0);
            int x = -l1[i].second-1;
            if(T[x]>T[cur]){
                cur = x;
            }
        }
        else{
            start[l1[i].second] = cur;
        }
    }
    

    vector<pair<int,int>> l2;
    for(int i=0;i<m;i++){
        l2.push_back({H[i],i});
    }
    for(int i=0;i<n;i++){
        l2.push_back({T[i],-i-1});
    }
    sort(l2.begin(),l2.end());
    vector<int> first(m);
    cur = n;
    for(int i=n+m-1;i>=0;i--){
        if(l2[i].second<0){
            cur = min(cur,-l2[i].second-1);
        }
        else{
            first[l2[i].second] = cur;
        }
    }


    vector<pair<int,int>> s1;
    for(int i=0;i<m-1;i++){
        int x;
        if(H[i]>H[i+1]){
            x = i;
        }
        else{
            x = i+1;
        }
        s1.push_back({first[x],-i-1});
    }
    for(int i=0;i<m;i++){
        s1.push_back({start[i],i});
    }
    sort(s1.begin(),s1.end());
    DSU dsu(m);
    for(int i=0;i<m;i++){
        ans.e.push_back(-1);
        ans.z.push_back(i);
    }
    for(int i=0;i<m;i++){
        parent.push_back(-1);
    }
    for(int i=0;i<2*m-1;i++){
        if(s1[i].second<0){
            dsu.join(-s1[i].second,-s1[i].second-1);
        }
        else{
            if(s1[i].second!=dsu.z[dsu.parent(s1[i].second)]){
                parent[s1[i].second] = dsu.z[dsu.parent(s1[i].second)];
                ans.join(s1[i].second,dsu.z[dsu.parent(s1[i].second)]);
            }
        }
    }
}

bool can_reach(int L, int R, int S, int D){
    return ans.parent(S)==ans.parent(D);
}

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