Submission #659918

#	Time	Username	Problem	Language	Result	Execution time	Memory
659918		Dec0Dedd	Walk (CEOI06_walk)	C++14	86 / 100	825 ms	61156 KiB

walk

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef long long ll;

const int N = 1e5+1;
const int S = 1e6+10;
const int K = 5e5+1;
const ll INF = 1e17+1;

int x, y, n;

vector<pii> p, bg[S];
set<int> s;
map<int, int> sc;

ll ans[4*K], par[4*K];
pll T[4*K][2];
bool L[4*K];

void push(int v) {
   for (int t=0; t<2; ++t) {
      T[2*v][t]=T[2*v+1][t]={INF, INF};
      L[2*v]=L[2*v+1]=true;
   }
   L[v]=false;
}

pll que(int v, int l, int r, int ql, int qr, int t) {
   if (l > qr || r < ql) return {INF, INF};
   if (l >= ql && r <= qr) return T[v][t];
   if (L[v]) push(v);
   int m=(l+r)/2;
   return min(
      que(2*v, l, m, ql, qr, t),
      que(2*v+1, m+1, r, ql, qr, t)
   );
}

void clear(int v, int l, int r, int ql, int qr) {
   if (l > qr || r < ql) return;
   if (l >= ql && r <= qr) {
      T[v][0]=T[v][1]={INF, INF};
      L[v]=true, push(v);
      return;
   }

   if (L[v]) push(v);
   int m=(l+r)/2;
   clear(2*v, l, m, ql, qr), clear(2*v+1, m+1, r, ql, qr);
   T[v][0]=min(T[2*v][0], T[2*v+1][0]);
   T[v][1]=min(T[2*v][1], T[2*v+1][1]);
}

void upd(int v, int l, int r, int pt, int t, pll x) {
   if (l == r) {
      assert(sc[p[x.second].second] == l);
      T[v][t]=min(T[v][t], x);
      return;
   }

   if (L[v]) push(v);
   int m=(l+r)/2;
   if (pt <= m) upd(2*v, l, m, pt, t, x);
   else upd(2*v+1, m+1, r, pt, t, x);
   T[v][t]=min(T[2*v][t], T[2*v+1][t]);
}

int lb(int x, int y) {
   int l=0, r=bg[x].size()-1, res=-1;
   while (l <= r) {
      int m=(l+r)/2;
      if (bg[x][m].second <= y) l=m+1, res=m;
      else r=m-1;
   }
   return res;
}

int ub(int x, int y) {
   int l=0, r=bg[x].size()-1, res=-1;
   while (l <= r) {
      int m=(l+r)/2;
      if (bg[x][m].first >= y) l=m+1, res=m;
      else r=m-1;
   }
   return res;
}

int main() {
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);
   cout.tie(NULL);

   cin>>x>>y>>n;
   p.push_back({0, 0}), p.push_back({x, y});
   s.insert(0), s.insert(y);
   memset(par, -1, sizeof(par));

   for (int i=1; i<=n; ++i) {
      int x1, y1, x2, y2;
      cin>>x1>>y1>>x2>>y2;
      s.insert(y1), s.insert(y2);

      bg[min(x1, x2)].push_back({min(y1, y2), max(y1, y2)});
      p.push_back({min(x1, x2)-1, max(y1, y2)+1});
      p.push_back({max(x1, x2)+1, max(y1, y2)+1});
      p.push_back({max(x1, x2)+1, min(y1, y2)-1});
      p.push_back({min(x1, x2)-1, min(y1, y2)-1});
   }

   for (auto u : p) s.insert(u.second);

   int i=1;
   for (auto u : s) sc[u]=i++;
   sort(p.begin(), p.end());

   int sz=p.size();
   clear(1, 1, K, 1, K);

   int g=0;
   for (auto u : p) {
      if (u.first == 0 && u.second == 0) break;
      else ++g;
   }

   upd(1, 1, K, sc[0], 0, {0, g});
   upd(1, 1, K, sc[0], 1, {0, g});
   ans[g]=0;

   int ptr=0, h=1e6;
   for (int x=0; x<=h; ++x) {
      for (auto &u : bg[x]) {
         if (u.second < u.first) swap(u.first, u.second);
         clear(1, 1, K, sc[u.first], sc[u.second]);
      }
      sort(bg[x].begin(), bg[x].end());

      while (ptr < sz) {
         if (p[ptr].first > x) break;
         if (ptr == g) {
            ++ptr;
            continue;
         }
         int y=p[ptr].second;

         pll low=que(1, 1, K, 1, sc[y], 0);
         pll up=que(1, 1, K, sc[y], K, 1);

         if (low.first+y <= up.first-y) {
            ans[ptr]=low.first+y+x, par[ptr]=low.second;
            int k=par[ptr];
            assert(ans[k]+abs(p[k].first-x)+abs(p[k].second-y) == ans[ptr]);
         } else {
            ans[ptr]=up.first-y+x, par[ptr]=up.second;
            int k=par[ptr];
            assert(ans[k]+abs(p[k].first-x)+abs(p[k].second-y) == ans[ptr]);
         }

         upd(1, 1, K, sc[y], 0, {ans[ptr]-y-x, ptr});
         upd(1, 1, K, sc[y], 1, {ans[ptr]+y-x, ptr});
         ++ptr;
      }
   }

   int idx=0;
   for (auto u : p) {
      if (u.first == x && u.second == y) break;
      else ++idx;
   }

   cout<<ans[idx]<<"\n";
   vector<pii> mv;

   int pr=idx;
   while (par[pr] != -1) {
      if (par[pr] == -1) assert(pr == idx);
      int x=p[pr].first, y=p[pr].second;

      if (p[par[pr]].second != y) mv.push_back({0, y-p[par[pr]].second});
      if (p[par[pr]].first != x) mv.push_back({x-p[par[pr]].first, 0});
      pr=par[pr];
   } assert((int)mv.size() <= h);
   reverse(mv.begin(), mv.end());

   cout<<mv.size()<<"\n";
   for (auto u : mv) cout<<u.first<<" "<<u.second<<"\n";
}

• Subtask 1: 86 / 100