Submission #1332135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1332135		tung04885	Walk (CEOI06_walk)	C++20	80 / 100	35 ms	5720 KiB

walk

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 100100
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define __buitin_popcount __builtin_popcountll
#define BIT(x,i) (((x)>>(i))&1ll)
#define MASK(i) (1ll<<(i))
#define left __left
#define right __right

template<class X,class Y> bool maximize(X &x,Y y)
{
    if(x<y)
    {
        x=y;
        return 1;
    }
    return 0;
}

template<class X,class Y> bool minimize(X &x,Y y)
{
    if(y<x)
    {
        x=y;
        return 1;
    }
    return 0;
}

const int inf=1e9+412009;
const ll INF=2e18+412009;

struct POINT
{
    int x,y;
    int id;

    void input(int i=0)
    {
        cin>>x>>y;
        id=i;
    }

    bool operator < (POINT other) const
    {
        return x==other.x ? y<other.y : x<other.x;
    }
};

double LEN(POINT a,POINT b)
{
    return abs(a.x-b.x)+abs(a.y-b.y);
}

struct RECT
{
    int top=0,bot=0,left=0,right=0;
    int id=0;

    void input(int i=0)
    {
        id=i;

        int x,y,u,v;

        cin>>x>>y>>u>>v;

        top=max(y,v);

        bot=min(y,v);

        right=max(x,u);

        left=min(x,u);
    }

    bool operator < (RECT other) const
    {
        return left<other.left;
    }
};

POINT T;
int n;
RECT a[MAX];

void nhap()
{
    T.input(1);

    int tmp;

    cin>>tmp;

    for(int i=1;i<=tmp;i++)
    {
        RECT vl;vl.input();

        if(T.x<=vl.right) continue;

        a[++n]=vl;
    }
}

ll dist[MAX][2];
pii trace[MAX][2];
set<pii> s;

void solve()
{
    memset(dist,0x3f,sizeof(dist));

    sort(a+1,a+n+1);

    s.insert({0,0});
    dist[0][0]=0;

    for(int i=1;i<=n;i++)
    {
        for(auto it=s.lower_bound({a[i].bot,-inf});it!=s.end()&&it->fi<=a[i].top;)
        {
            int id=abs(it->se),type=it->se>0;

            if(minimize(dist[i][0],a[i].left-a[id].left+abs(a[i].bot-1-it->fi)+dist[id][type])) trace[i][0]=*it;

            if(minimize(dist[i][1],a[i].left-a[id].left+abs(a[i].top+1-it->fi)+dist[id][type])) trace[i][1]=*it;

            auto it1=it;

            it++;

            s.erase(it1);
        }

        if(dist[i][0]<INF) s.insert({a[i].bot-1,-i});
        if(dist[i][1]<INF) s.insert({a[i].top+1,i});
    }

    ll ans=INF;

    for(pii it:s)
    {
        int id=abs(it.se),type=it.se>0;

        if(minimize(ans,dist[id][type]+abs(it.fi-T.y)+abs(a[id].left-T.x))) trace[n+1][0]=it;
    }

    cout<<ans<<'\n';

    vector<pii> tracing;

    #define PUSH(a,b) if(!tracing.empty()) {if(tracing.back().fi==0&&a==0) tracing.back().se+=b;else if(tracing.back().se==0&&b==0)tracing.back().fi+=a;else tracing.push_back({a,b});}else tracing.push_back({a,b});

    int u=n+1,id=0;

    while(u!=0)
    {
        int v=abs(trace[u][id].se);
        int type=trace[u][id].se>0;

        int delta_x=T.x-a[v].left-1,delta_y=T.y-trace[u][id].fi;

        PUSH(1,0);
        PUSH(0,delta_y);
        PUSH(delta_x,0);

        int newx=a[v].left,newy=type==0 ? a[v].bot-1 : a[v].top+1;

        T={newx,newy,0};

        u=v;
    }

    reverse(all(tracing));

    cout<<"1\n0 0"<<'\n';

    //for(pii p:tracing) cout<<p.fi<<' '<<p.se<<'\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    nhap();
    solve();

    return 0;
}

• Subtask 1: 80 / 100