Submission #659875

#	Time	Username	Problem	Language	Result	Execution time	Memory
659875		Dec0Dedd	Walk (CEOI06_walk)	C++14	0 / 100	737 ms	63328 KiB

walk

#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e5+1;
const int S = 1e6+10;
const int K = 4e5+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[v]) push(v);
   if (l >= ql && r <= qr) return T[v][t];
   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[v]) push(v);
   if (l >= ql && r <= qr) {
      T[v][0]=T[v][1]={INF, INF};
      L[v]=true, push(v);
      return;
   }
   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 p, int t, pll x) {
   if (l == r) {
      T[v][t]=min(T[v][t], x);
      return;
   }

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

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});
   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, sz, 1, sz);

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

   int ptr=1, h=1e6;
   for (int x=1; x<=h; ++x) {
      while (ptr < sz) {
         if (p[ptr].first > x) break;
         int y=p[ptr].second;

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

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

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

      for (auto &u : bg[x]) {
         if (u.second < u.first) swap(u.first, u.second);
         clear(1, 1, sz, sc[u.first], sc[u.second]);
      }
   }

   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) {
      int x=p[pr].first, y=p[pr].second;
      if (p[par[pr]].first != x) mv.push_back({x-p[par[pr]].first, 0});
      if (p[par[pr]].second != y) mv.push_back({0, y-p[par[pr]].second});
      pr=par[pr];
   } assert((int)mv.size() <= h);

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

• Subtask 1: 0 / 100