Submission #1266804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266804		dima2101	Maze (JOI23_ho_t3)	C++20	86 / 100	2098 ms	203280 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

struct Node{
    int left;
    int max;
    Node(int left,int max):left(left),max(max){};
    Node(){
        max = 0;
        left = 0;
    }
};
struct SegTree{
    int n;
    std::vector<Node> t;
    SegTree(int n):n(n){
        t.resize(4 * n);
        build(0,0,n);
    }
    SegTree() = default;

    Node mer(Node a,Node b){
        if(a.max == 0)return b;
        if(b.max == 0)return a;
        a.left = std::min(a.left,b.left);
        return a;
    }

    void build(int i,int l,int r){
        if(l == r - 1){
            t[i].max = 1;
            t[i].left = l;
            return;
        }
        int mid = (l + r) / 2;
        build(2 * i + 1,l,mid);
        build(2 * i + 2,mid,r);
        t[i] = mer(t[2 * i + 1],t[2 * i + 2]);
    }

    void upd(int i,int l,int r,int pos){
        if(l == r - 1){
            t[i].max = 0;
            t[i].left = 0;
            return;
        }
        int mid = (l + r) / 2;
        if(pos >= mid){
            upd(2 * i + 2,mid,r,pos);
        }else{
            upd(2 * i + 1,l,mid,pos);
        }
        // std::cout<<t[i].left<<' '<<t[i].max<<"sdjf "<<l<<' '<<r<<' '<<pos<<std::endl;
        t[i] = mer(t[2 * i + 1],t[2 * i + 2]);
        // std::cout<<t[i].left<<' '<<t[i].max<<"dsjf "<<l<<' '<<r<<' '<<pos<<std::endl;

    }

    Node query(int i,int l,int r,int ql,int qr){
        if(ql == qr)return Node();
        if(l >= ql && r <= qr){
            return t[i];
        }
        if(l >= qr || ql >= r)return Node();
        int mid = (l + r) / 2;
        return mer(query(2 * i + 1,l,mid,ql,qr),query(2 * i + 2,mid,r,ql,qr));
    }
};


void del(int x,int y,std::vector<SegTree>& hor,
    std::vector<SegTree>& vert,int r,int c){
        // std::cout<<x<<' '<<y<<std::endl;
    hor[x].upd(0,0,c,y);
    vert[y].upd(0,0,r,x);
    // std::cout<<"AA "<<' '<<vert[y].query(0,0,r,x,x + 2).max<<std::endl;
}

struct Event{
    bool type;
    int ind;
    int l,r;
    Event(bool type,int ind,int l,int r):type(type),ind(ind),l(l),r(r){};
    Event() = default;
};

signed
main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int r,c,n;
    std::cin>>r>>c>>n;

    std::pair<int,int> start;
    std::cin>>start.first>>start.second;
    start.first--;
    start.second--;
    std::pair<int,int> stop;
    std::cin>>stop.first>>stop.second;
    stop.first--;
    stop.second--;

    std::vector<std::vector<char>> a(r,std::vector<char>(c));
    for(int  i=0 ;i < r;i++){
        for(int j =0 ;j < c;j++){
            std::cin>>a[i][j];
        }
    }


    std::vector<std::vector<int>> dist(r,std::vector<int>(c,1e8));

    std::vector<SegTree> hor(r);
    for(int i =0 ;i < r;i++){
        hor[i] = SegTree(c);
    }
    std::vector<SegTree> vert(c);
    for(int i =0 ;i <c;i++){
        vert[i] = SegTree(r);
    }
    // std::cout<<"dhjf"<<std::endl;

    std::deque<std::pair<int,int>> help;
    help.push_front(start);
    dist[start.first][start.second] = 0;
    del(start.first,start.second,hor,vert,r,c);
    while(help.size() > 0){
        auto v = help.front();
        // std::cout<<v.first<<' '<<v.second<<' '<<dist[v.first][v.second]<<std::endl;
        help.pop_front();

        std::vector<int> dx = {0,0,-1,1};
        std::vector<int> dy = {1,-1,0,0};
        for(int i =0 ;i < dx.size();i++){
            if(v.first + dx[i] >= 0 && v.first + dx[i] < r && 
                v.second + dy[i] >=0  && v.second + dy[i] < c && 
                dist[v.first + dx[i]][v.second + dy[i]] > dist[v.first][v.second] && 
                a[v.first + dx[i]][v.second + dy[i]] == '.'){
                    dist[v.first + dx[i]][v.second + dy[i]] = dist[v.first][v.second];
                    del(v.first + dx[i],v.second + dy[i],hor,vert,r,c);
                    help.push_front({v.first + dx[i],v.second + dy[i]});
            }
        }

        int abs_x = std::abs(v.first - stop.first);
        int abs_y = std::abs(v.second - stop.second);
        if(abs_x <= n && abs_y <= n && abs_x + abs_y != 2 * n){
            if(dist[stop.first][stop.second] > dist[v.first][v.second] + 1){
                // std::cout<<dist[v.first][v.second] + 1<<std::endl;
                dist[stop.first][stop.second] = dist[v.first][v.second] + 1;
                del(stop.first,stop.second,hor,vert,r,c);
            }
        }


        dx = {v.first - n + 1,v.first + n - 1,v.first - n + 1,v.first + n - 1};
        dy = {v.second - n + 1,v.second - n + 1,v.second + n - 1,v.second + n - 1};
        for(int i = 0 ;i < dx.size();i++){
            if(dx[i] >= 0 && dx[i] < r && dy[i] >=0 && dy[i] < c){
                if(dist[dx[i]][dy[i]] > dist[v.first][v.second] + 1){
                    dist[dx[i]][dy[i]] = dist[v.first][v.second] + 1;
                    del(dx[i],dy[i],hor,vert,r,c);
                    help.push_back({dx[i],dy[i]});
                }
            }
        }


        std::vector<Event> all;
        if(v.second + n < c){
            all.push_back(Event(0,v.second + n,std::max(0,v.first - n + 1),
            std::min(r - 1,v.first + n - 1)));
        }
        if(v.second - n >= 0){
            all.push_back(Event(0,v.second - n,
                std::max(0,v.first - n + 1),std::min(r - 1,v.first + n - 1)));
        }
        if(v.first + n < r){
            all.push_back(Event(1,v.first + n,std::max(0,v.second - n + 1),std::min(c - 1,v.second + n - 1)));
        }
        if(v.first - n >= 0){
            all.push_back(Event(1,v.first - n,std::max(0,v.second - n + 1),std::min(c - 1,v.second + n - 1)));
        }

        

        for(auto now:all){
            // std::cout<<now.ind<<' '<<now.type<<' '<<now.l<<' '<<now.r<<std::endl;
            if(now.type == 0){
                Node tmp = Node();
                do{
                    // std::cout<<"dsjf"<<std::endl;
                    // std::cout<<now.l<<' '<<now.r<<' '<<r<<' '<<now.ind<<' '<<vert.size()<<std::endl;
                    tmp = vert[now.ind].query(0,0,r,now.l,now.r + 1);
                    // std::cout<<tmp.left<<' '<<tmp.max<<' '<<vert[now.ind].query(0,0,r,tmp.left,tmp.left + 1).max<<std::endl;
                    if(tmp.max == 0)break;
                    if(dist[tmp.left][now.ind] > dist[v.first][v.second] + 1){
                        dist[tmp.left][now.ind] = dist[v.first][v.second] + 1;
                        help.push_back({tmp.left,now.ind});
                    }

                    del(tmp.left,now.ind,hor,vert,r,c);
                    // std::cout<<tmp.left<<' '<<tmp.max<<' '<<vert[now.ind].query(0,0,r,now.l,now.r + 1).max<<std::endl;

                    // exit(0);
                }while(tmp.max != 0);
            }else{
                Node tmp = Node();
                do{
                    // std::cout<<now.l<<' '<<now.r<<' '<<now.type<<' '<<' '<<now.ind<<std::endl;
                    tmp = hor[now.ind].query(0,0,c,now.l,now.r + 1);
                    if(tmp.max == 0)break;
                    if(dist[now.ind][tmp.left] > dist[v.first][v.second] + 1){
                        dist[now.ind][tmp.left] = dist[v.first][v.second] + 1;
                        help.push_back({now.ind,tmp.left});
                    }
                    del(now.ind,tmp.left,hor,vert,r,c);

                }while(tmp.max != 0);
            }
        }
        // std::cout<<"djf"<<std::endl;

    }
    // for(int i=0;i < r;i++){
    //     for(int j =0 ;j < c;j++){
    //         std::cout<<dist[i][j]<<' ';
    //     }
    //     std::cout<<std::endl;
    // }
    std::cout<<dist[stop.first][stop.second];
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 16 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 19 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6