oj.uz

Submission #659874

# Submission time Handle Problem Language Result Execution time Memory
659874 2022-11-19T15:41:40 Z Dec0Dedd Connect (CEOI06_connect) C++14
0 / 100
 22 ms 36352 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 36224 KB Wrong score! (28, expected 26)
2 Incorrect 19 ms 36352 KB Wrong score! (26, expected 40)
3 Incorrect 19 ms 36292 KB Wrong score! (36, expected 74)
4 Incorrect 19 ms 36308 KB Wrong score! (30, expected 28)
5 Incorrect 18 ms 36324 KB Wrong score! (50, expected 102)
6 Incorrect 19 ms 36344 KB Wrong score! (90, expected 112)
7 Incorrect 19 ms 36220 KB Wrong score! (48, expected 72)
8 Incorrect 19 ms 36228 KB Wrong score! (68, expected 94)
9 Incorrect 19 ms 36324 KB Wrong score! (72, expected 132)
10 Incorrect 22 ms 36328 KB Wrong score! (94, expected 208)
11 Incorrect 19 ms 36308 KB Wrong score! (64, expected 106)
12 Incorrect 19 ms 36260 KB Wrong score! (98, expected 268)
13 Incorrect 19 ms 36308 KB Wrong score! (72, expected 208)
14 Incorrect 19 ms 36308 KB Wrong score! (100, expected 462)
15 Incorrect 20 ms 36220 KB Wrong score! (76, expected 422)
16 Incorrect 20 ms 36344 KB Wrong score! (94, expected 664)
17 Incorrect 19 ms 36308 KB Wrong score! (66, expected 288)
18 Incorrect 19 ms 36348 KB Wrong score! (104, expected 296)
19 Incorrect 19 ms 36224 KB Wrong score! (104, expected 212)
20 Incorrect 21 ms 36336 KB Wrong score! (104, expected 374)