Submission #1111120

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1111120	2024-11-11T14:34:00 Z	doducanh	Walk (CEOI06_walk)	C++14	100 / 100	106 ms	13484 KB

walk

///breaker
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
#define lc (id<<1)
#define rc ((id<<1)^1)
const int maxn=1e5+7;
struct info
{
    int x1,x2,y1,y2;
    int x;
    int id;
    int link1,link2;
};
struct event
{
    int id,y,type;
};
bool cmpx2(const info &a,const info &b)
{
    return a.x2<b.x2;
}
struct segtree
{
    vector<int>t;
    int n;
    segtree(int N)
    {
        n=N;
        t.resize(4*N,-1);
    }
    void add(int id,int l,int r,int u,int val)
    {
        if(l>u||r<u)return;
        if(l==r){
            t[id]=val;
            return;
        }
        int m=(l+r)/2;
        if(u<=m)add(lc,l,m,u,val);
        else add(rc,m+1,r,u,val);
        t[id]=max(t[lc],t[rc]);
    }
    int get(int id,int l,int r,int u)
    {
        if(l>u)return -1;
        if(r<=u)return t[id];
        int m=(l+r)/2;
        return max(get(lc,l,m,u),get(rc,m+1,r,u));
    }
    void era(int id,int l,int r,int u)
    {
        if(l>u||r<u)return;
        if(l==r){
            t[id]=-1;
            return;
        }
        int m=(l+r)/2;
        if(u<=m)era(lc,l,m,u);
        else era(rc,m+1,r,u);
        t[id]=max(t[lc],t[rc]);
    }
    void add(int u,int val){add(1,0,n,u,val);}
    int get(int u){return get(1,0,n,u);}
    void era(int u){era(1,0,n,u);}
};
int X,Y;
int n;
ii dp[maxn];
vector<ii>sol;
vector<info>a(n);
void backtrack(int &link,int &ans)
{
    if(link==-1){
        sol.push_back({X,0}),X=0;
        sol.push_back({0,Y}),Y=0;
        return;
    }
    if( ans == X-a[link].x2-1 + abs( Y - a[link].y1+1 ) + dp[link].first ) {
         int dx = X - a[link].x2-1;
         int dy = Y - a[link].y1+1;
         if( dx ) { sol.push_back( pair<int,int> (dx, 0) ); X -= dx; }
         if( dy ) { sol.push_back( pair<int,int> (0, dy) ); Y -= dy; }
         ans = dp[link].first;
         link = a[link].link1;
      } else {
         int dx = X - a[link].x2-1;
         int dy = Y - a[link].y2-1;
         if( dx ) { sol.push_back( pair<int,int> (dx, 0) ); X -= dx; }
         if( dy ) { sol.push_back( pair<int,int> (0, dy) ); Y -= dy; }
         ans = dp[link].second;
         link = a[link].link2;
      }
}
void solve(void){
    cin>>X>>Y;
    cin>>n;
    a.resize(n);
    for(int i=0;i<n;i++){
        cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2;
        a[i].link1=-1;
        a[i].link2=-1;
        if(a[i].x1>a[i].x2)swap(a[i].x1,a[i].x2);
        if(a[i].y1>a[i].y2)swap(a[i].y1,a[i].y2);
    }
    sort(a.begin(),a.end(),cmpx2);
    int cnt=0;
    int lastx=-1;
    vector<event>events;
    for(int i=0;i<n;i++){
        a[i].id=i;
        if(a[i].x2!=lastx){
            cnt++;
        }
        a[i].x=cnt;
        lastx=a[i].x2;
        events.push_back({i,a[i].y1,0});
        events.push_back({i,a[i].y1-1,1});
        events.push_back({i,a[i].y2+1,2});
        events.push_back({i,a[i].y2,3});
    }
    sort(events.begin(),events.end(),[&](event &a, event &b){
         return (a.y<b.y)||(a.y==b.y&&a.type<b.type);
    });
    segtree t(cnt+1);
    for(event tmp:events){
        if(tmp.type==0){
            t.add(a[tmp.id].x,tmp.id);
        }
        else if(tmp.type==1){
            a[tmp.id].link1=t.get(a[tmp.id].x);
        }
        else if(tmp.type==2){
            a[tmp.id].link2=t.get(a[tmp.id].x);
        }
        else{
            t.era(a[tmp.id].x);
        }
    }
    for(int i=0;i<n;i++){
        int j=a[i].link1;
        if(j==-1){
            dp[i].fi=a[i].x2+1+abs(a[i].y1-1);
        }
        else{
            dp[i].fi=min(dp[j].fi+a[i].x2-a[j].x2+abs(a[i].y1-1-a[j].y1+1),dp[j].se+a[i].x2-a[j].x2+abs(a[i].y1-1-a[j].y2-1));
        }
        j=a[i].link2;
        if(j==-1){
            dp[i].se=a[i].x2+1+abs(a[i].y2+1);
        }
        else{
            dp[i].se=min(dp[j].fi+a[i].x2-a[j].x2+abs(a[i].y2+1-a[j].y1+1),dp[j].se+a[i].x2-a[j].x2+abs(a[i].y2+1-a[j].y2-1));
        }
    }
    int ans=X+abs(Y);
    int link=-1;
    for(int i=n-1;i>=0;i--){
        if(a[i].x2<X&&a[i].y1<=Y&&Y<=a[i].y2){
            link=i;
            break;
        }
    }
    if(link!=-1){
        ans=min(X-a[link].x2-1+abs(Y-a[link].y1+1)+dp[link].fi,X-a[link].x2-1+abs(Y-a[link].y2-1)+dp[link].se);
    }
    cout<<ans<<"\n";
    if(link!=-1){
        while(X!=0||Y!=0){
            backtrack(link,ans);
        }
    }
    cout<<sol.size()<<"\n";
    for(int i=sol.size()-1;i>=0;i--){
        cout<<sol[i].fi<<" "<<sol[i].se<<"\n";
    }
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        solve();
    }
    // you should actually read the stuff at the bottom
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	504 KB	Output is correct
4	Correct	2 ms	592 KB	Output is correct
5	Correct	86 ms	12472 KB	Output is correct
6	Correct	30 ms	3968 KB	Output is correct
7	Correct	58 ms	6852 KB	Output is correct
8	Correct	106 ms	12460 KB	Output is correct
9	Correct	101 ms	13368 KB	Output is correct
10	Correct	106 ms	13484 KB	Output is correct