Submission #395652

#	Time	Username	Problem	Language	Result	Execution time	Memory
395652		usachevd0	Road Construction (JOI21_road_construction)	C++17	100 / 100	3025 ms	414432 KiB

road_construction

#pragma gcc optimize("Ofast")
#pragma gcc optimize("O3")
#pragma gcc optimize("fast-math")
#pragma gcc optimize("unroll-loops")
#pragma gcc optimize("no-stack-protector")
#pragma gcc target("avx,avx2,ffa,sse,sse2,sse4.2")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) {
  return y < x ? (x = y, true) : false; 
}
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) {
  return y > x ? (x = y, true) : false;
}
void debug_out() {
  cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
  cerr << ' ' << A;
  debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
  for (int i = 0; i < n; ++i) {
    cerr << a[i] << ' ';
  }
  cerr << endl;
}
#ifdef DEBUG
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
  #define debug(...) 1337
  #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T> &v) {
  for (auto& x : v) {
    stream << x << ' ';
  }
  return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
  return stream << p.first << ' ' << p.second;
}

const int INF32 = 2e9 + 1337 * 228;
const int maxN = 250010;
int n, K;
int X[maxN], Y[maxN];
pii ordX[maxN], ordY[maxN];
int posX[maxN], posY[maxN];

int sgt[maxN][2];

namespace psgt {
  const int maxV = 4e7 + 1337;
  int V = 1;
  int L[maxV], R[maxV];
  pii mn[maxV];

  void init() {
    V = 1;
    mn[0] = {INF32, -1};
  }
  int clone(int v) {
    L[V] = L[v];
    R[V] = R[v];
    mn[V] = mn[v];
    return V++;
  }
  int mdf(int v, int vl, int vr, int pos, int val) {
    int nv = clone(v);
    if (vl == vr) {
      mn[nv] = {val, vl};
      return nv;
    }
    int vm = (vl + vr) >> 1;
    if (pos <= vm) {
      L[nv] = mdf(L[nv], vl, vm, pos, val);
    } else {
      R[nv] = mdf(R[nv], vm + 1, vr, pos, val);
    }
    mn[nv] = min(mn[L[nv]], mn[R[nv]]);
    return nv;
  }
  pii rmq(int v, int vl, int vr, int l, int r) {
    if (l > r || vr < l || r < vl) return {INF32, -1};
    if (l <= vl && vr <= r) return mn[v];
    int vm = (vl + vr) >> 1;
    return min(rmq(L[v], vl, vm, l, r), rmq(R[v], vm + 1, vr, l, r));
  }
}

void sdebug(int v) {
  for (int i = 0; i < n; ++i) {
    cerr << psgt::rmq(v, 0, n - 1, i, i).fi << ' ';
  }
  cerr << endl;
}

int32_t main() {
#ifdef DEBUG
  freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);

  psgt::init();
  cin >> n >> K;
  for (int i = 0; i < n; ++i) {
    cin >> X[i] >> Y[i];
    ordX[i] = {X[i], i};
    ordY[i] = {Y[i], i};
  }
  sort(ordX, ordX + n);
  for (int i = 0; i < n; ++i) {
    posX[ordX[i].se] = i;
  }
  sort(ordY, ordY + n);
  for (int i = 0; i < n; ++i) {
    posY[ordY[i].se] = i;
  }
  //mdebug(ordX, n);
  //mdebug(ordY, n);
  
  multiset<pair<ll, pii>> pq;
  for (int t = 0; t < n; ++t) {
    int i = ordX[t].se;
    sgt[t + 1][0] = psgt::mdf(sgt[t][0], 0, n - 1, posY[i], -X[i] + Y[i]);
    sgt[t + 1][1] = psgt::mdf(sgt[t][1], 0, n - 1, posY[i], -X[i] - Y[i]);
    //debug(t);
    //sdebug(sgt[t + 1][0]);
    //sdebug(sgt[t + 1][1]);
    {
      auto res = psgt::rmq(sgt[t][0], 0, n - 1, posY[i] + 1, n - 1);
      if (res.fi < INF32) {
        sgt[t][0] = psgt::mdf(sgt[t][0], 0, n - 1, res.se, INF32);
        pq.insert(mp(res.fi + (ll)X[i] - (ll)Y[i], mp(i, 0)));
      }
    }
    {
      auto res = psgt::rmq(sgt[t][1], 0, n - 1, 0, posY[i] - 1);
      if (res.fi < INF32) {
        sgt[t][1] = psgt::mdf(sgt[t][1], 0, n - 1, res.se, INF32);
        pq.insert(mp(res.fi + (ll)X[i] + (ll)Y[i], mp(i, 1)));
      }
    }
  }
  for (int e = 0; e < K; ++e) {
    cout << pq.begin()->fi << '\n';
    int i = pq.begin()->se.fi;
    int d = pq.begin()->se.se;
    pq.erase(pq.begin());
    int& ver = sgt[posX[i]][d];
    if (d == 0) {
      auto res = psgt::rmq(ver, 0, n - 1, posY[i] + 1, n - 1);
      if (res.fi < INF32) {
        //sdebug(ver);
        //debug(res.se);
        ver = psgt::mdf(ver, 0, n - 1, res.se, INF32);
        //sdebug(ver);
        pq.insert(mp((ll)res.fi + (ll)X[i] - (ll)Y[i], mp(i, 0)));
      }
    } else {
      auto res = psgt::rmq(ver, 0, n - 1, 0, posY[i] - 1);
      if (res.fi < INF32) {
        //sdebug(ver);
        //debug(res);
        ver = psgt::mdf(ver, 0, n - 1, res.se, INF32);
        //sdebug(ver);
        pq.insert(mp((ll)res.fi + (ll)X[i] + (ll)Y[i], mp(i, 1)));
      }
    }
  }
  
    
  return 0;
}

Compilation message (stderr)

road_construction.cpp:1: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    1 | #pragma gcc optimize("Ofast")
      | 
road_construction.cpp:2: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    2 | #pragma gcc optimize("O3")
      | 
road_construction.cpp:3: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    3 | #pragma gcc optimize("fast-math")
      | 
road_construction.cpp:4: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    4 | #pragma gcc optimize("unroll-loops")
      | 
road_construction.cpp:5: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    5 | #pragma gcc optimize("no-stack-protector")
      | 
road_construction.cpp:6: warning: ignoring #pragma gcc target [-Wunknown-pragmas]
    6 | #pragma gcc target("avx,avx2,ffa,sse,sse2,sse4.2")
      |

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35