Submission #395613

#	Time	Username	Problem	Language	Result	Execution time	Memory
395613		usachevd0	Road Construction (JOI21_road_construction)	C++17	32 / 100	10048 ms	109984 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;
}

mt19937 rng(time(0));
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)

const int maxN = 250105;
int n;
int X[maxN], Y[maxN], U[maxN], V[maxN], compr_V[maxN];
int valV[maxN];
int m;
pii ordU[maxN];
int ver[maxN];

int need[maxN];
ll ans[2 * maxN];

ll remember_r[maxN];

inline int v_geq(ll x) {
  /*int vl = -1;
  int vr = m;
  while (vr - vl > 1) {
    int vm = (vl + vr) >> 1;
    if (valV[vm] >= x) {
      vr = vm;
    } else {
      vl = vm;
    }
  }
  return vr;*/  
  return lower_bound(valV, valV + m, x) - valV;
}
inline int v_leq(ll x) {
  /*int vl = -1;
  int vr = m;
  while (vr - vl > 1) {
    int vm = (vl + vr) >> 1;
    if (valV[vm] <= x) {
      vl = vm;
    } else {
      vr = vm;
    }
  }
  return vl;*/
  return upper_bound(valV, valV + m, x) - valV - 1;
}
inline int u_geq(ll x) {
  int vl = -1;
  int vr = n;
  while (vr - vl > 1) {
    int vm = (vl + vr) >> 1;
    if (ordU[vm].fi >= x) {
      vr = vm;
    } else {
      vl = vm;
    }
  }
  return vr;
  //return lower_bound(ordU, ordU + n, mp(x, -1)) - ordU;
}
inline int u_leq(ll x) {
  int vl = -1;
  int vr = n;
  while (vr - vl > 1) {
    int vm = (vl + vr) >> 1;
    if (ordU[vm].fi <= x) {
      vl = vm;
    } else {
      vr = vm;
    }
  }
  return vl;
  //return upper_bound(ordU, ordU + n, mp(x, 1000000000)) - ordU - 1;
}

namespace psgt {
  const int maxV = 5500007;
  int V = 1;
  int L[maxV], R[maxV], S[maxV];

  inline int newNode() {
    return V++;
  }
  inline int clone(int v) {
    assert(V < maxV);
    L[V] = L[v];
    R[V] = R[v];
    S[V] = S[v];
    return V++;
  }
  inline int add(int v, int vl, int vr, int i) {
    int nv = clone(v);
    ++S[nv];
    if (vl != vr) {
      int vm = (vl + vr) >> 1;
      if (i <= vm) {
        L[nv] = add(L[nv], vl, vm, i);
      } else {
        R[nv] = add(R[nv], vm + 1, vr, i);
      }
    }
    return nv;
  }
  inline int suf_sum(int v1, int v2, int vl, int vr, int l) {
    int ans = 0;
    while (vl < vr) {
      int vm = (vl + vr) >> 1;
      if (l <= vm) {
        ans += S[R[v1]] - S[R[v2]];
        v1 = L[v1];
        v2 = L[v2];
        vr = vm;
      } else {
        v1 = R[v1];
        v2 = R[v2];
        vl = vm + 1;
      }
    }
    return ans + S[v1] - S[v2];
  }
  inline int pref_sum(int v1, int v2, int vl, int vr, int r) {
    int ans = 0;
    while (vl < vr) {
      int vm = (vl + vr) >> 1;
      if (r > vm) {
        ans += S[L[v1]] - S[L[v2]];
        v1 = R[v1];
        v2 = R[v2];
        vl = vm + 1;
      } else {
        v1 = L[v1];
        v2 = L[v2];
        vr = vm;
      }
    }
    return ans + S[v1] - S[v2];    
  }
  int rsq_dif(int v1, int v2, int l, int r) {
    //debug(v1, v2, vl, vr, l, r);
    /*//if (l > r || vr < l || r < vl) return 0;
    if (l <= vl && vr <= r) {
      return S[v1] - S[v2];
    }
    int vm = (vl + vr) >> 1;
    if (l > vm) return rsq_dif(R[v1], R[v2], vm + 1, vr, l, r);
    if (r <= vm) return rsq_dif(L[v1], L[v2], vl, vm, l, r);
    return rsq_dif(R[v1], R[v2], vm + 1, vr, l, r) + rsq_dif(L[v1], L[v2], vl, vm, l, r);

    int ans = 0;
    if (l <= vm) ans += rsq_dif(L[v1], L[v2], vl, vm, l, r);
    if (r >= vm + 1) ans += rsq_dif(R[v1], R[v2], vm + 1, vr, l, r);
    return ans;*/

    int vl = 0;
    int vr = m - 1;
    while (true) {
      int vm = (vl + vr) >> 1;
      //debug(vl, vr, vm);
      if (vl < vr && l > vm) {
        v1 = R[v1];
        v2 = R[v2];
        vl = vm + 1;
        continue;
      }
      if (vl < vr && r <= vm) {
        v1 = L[v1];
        v2 = L[v2];
        vr = vm;
        continue;
      }
      if (vl == l && vr == r) return S[v1] - S[v2];
      return suf_sum(L[v1], L[v2], vl, vm, l) + pref_sum(R[v1], R[v2], vm + 1, vr, r);
      break;
    }
  }
}

void prec() {
  for (int i = 0; i < n; ++i) {
    ordU[i] = {U[i], i};
    valV[i] = V[i];
  }
  sort(ordU, ordU + n);
  sort(valV, valV + n);
  m = unique(valV, valV + n) - valV;

  ver[0] = 0;
  for (int t = 0; t < n; ++t) {
    int i = ordU[t].se;
    compr_V[i] = v_geq(V[i]);
    ver[t + 1] = psgt::add(ver[t], 0, m - 1, compr_V[i]); 
  }
}

int ask;

int Count(int i, ll L) {
  ++ask;
  int ul = u_geq(U[i] - L);
  int ur = u_leq(U[i] + L);
  if (ul > ur) return 0;
  int vl = v_geq(V[i] - L);
  int vr = v_leq(V[i] + L);
  if (vl > vr) return 0;

  //return rng();

  return psgt::rsq_dif(ver[ur + 1], ver[ul], vl, vr);

  /*int ans = 0;
  for (int j = 0; j < n; ++j) {
    if (U[i] - L <= U[j] && U[j] <= U[i] + L &&
        V[i] - L <= V[j] && V[j] <= V[i] + L)
    {
      ++ans;
    }
  }
  return ans;*/
}

const int BPTHRESHOLD = 10;
const double BPCONST = 0.2;
ll BP(int i, int k, ll custom_l = 0) {
  assert(k > 0);
  ll vl = custom_l;
  ll vr = remember_r[i];//4e9 + 1337 * 228;
  while (vr - vl > 1) {
    ll vm;
    if (vr - vl > BPTHRESHOLD) {
      vm = vl + (vr - vl) * BPCONST;
    } else {
      vm = (vl + vr) >> 1;
    }
    int cnt = Count(i, vm) - 1;
    if (cnt >= n - 1) {
      remember_r[i] = vm;
    }
    if (cnt >= k) {
      vr = vm;
    } else {
      vl = vm;
    }
  }
  return vr;
}

ll VL[maxN], VR[maxN], VM[maxN];
int ANS[maxN];
int vvl[maxN], vvr[maxN];
int uul[maxN], uur[maxN];
int qcnt[maxN], qhead[maxN], qord[2 * maxN];
vector<int> query[maxN];

namespace fnw {
  int f[maxN];
  void reset() {
    memset(f, 0, sizeof f);
  }
  void add(int i) {
    for (i += 1; i <= n; i += i & -i) {
      ++f[i];
    }
  }
  int prf(int i) {
    int ans = 0;
    for (++i; i >= 1; i -= i & -i) {
      ans += f[i];
    }
    return ans;
  }
  int rsq(int l, int r) {
    return prf(r) - prf(l - 1);
  }
}

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

  int K;
  cin >> n >> K;
  K *= 2;
  for (int i = 0; i < n; ++i) {
    cin >> X[i] >> Y[i];
    U[i] = X[i] + Y[i];
    V[i] = Y[i] - X[i];
    remember_r[i] = (ll)4e9 + 1337;
  }
  prec();
  debug(Time);
  
  for (int i = 0; i < n; ++i) {
    VL[i] = VR[i] - 1;
    VR[i] = remember_r[i];
  }
  while (true) {
    int found = 0;
    fill(qcnt, qcnt + n + 1, 0);
    for (int i = 0; i < n; ++i) {
      if (VR[i] - VL[i] > 1) {
        ++found;
        if (VR[i] - VL[i] > BPTHRESHOLD) {
          VM[i] = VL[i] + (VR[i] - VL[i]) * BPCONST;
        } else {
          VM[i] = (VL[i] + VR[i]) >> 1;
        }
        ll L = VM[i];
        uul[i] = u_geq(U[i] - L);
        uur[i] = u_leq(U[i] + L);
        ++qcnt[uul[i]];
        ++qcnt[uur[i] + 1];
        //query[uul[i]].push_back(-i - 1);
        //query[uur[i] + 1].push_back(i);
        vvl[i] = v_geq(V[i] - L);
        vvr[i] = v_leq(V[i] + L);
        ANS[i] = 0;
      }
    }
    if (!found) break;
    qhead[0] = 0;
    for (int t = 1; t <= n; ++t) {
      qhead[t] = qhead[t - 1] + qcnt[t - 1];
    }
    for (int i = 0; i < n; ++i) {
      if (VR[i] - VL[i] > 1) {
        qord[qhead[uul[i]]++] = -i - 1;
        qord[qhead[uur[i] + 1]++] = i;
      }
    }
    for (int t = 0; t <= n; ++t) {
      qhead[t] -= qcnt[t];
    }
    //mdebug(qord, 2 * found);
    fnw::reset();
    for (int t = 0; t <= n; ++t) {
      for (int qptr = qhead[t]; qptr < qhead[t] + qcnt[t]; ++qptr) {
        int f = qord[qptr];
        int i, sgn;
        if (f >= 0) {
          i = f;
          sgn = 1;
        } else {
          i = -f - 1;
          sgn = -1;
        }
        ++ask;
        ANS[i] += sgn * fnw::rsq(vvl[i], vvr[i]);
      }
      /*for (int f : query[t]) {
        int i, sgn;
        if (f >= 0) {
          i = f;
          sgn = 1;
        } else {
          i = -f - 1;
          sgn = -1;
        }
        ANS[i] += sgn * fnw::rsq(vvl[i], vvr[i]);
      }*/
      //debug(t, qhead[t], qhead[t] + qcnt[t], query[t]);
      //query[t].clear();

      if (t < n) {
        int i = ordU[t].se;
        fnw::add(compr_V[i]);
      }
    }
    for (int i = 0; i < n; ++i) {
      if (VR[i] - VL[i] > 1) {
        if (ANS[i] >= 2) {
          VR[i] = VM[i];
        } else {
          VL[i] = VM[i];
        }
      }
    }
  }
  /*for (int i = 0; i < n; ++i) {
    VR[i] = BP(i, 1);
  }*/
  debug(Time);
  debug(ask / 1e6);
  
  fill(need, need + n, 1);
  multiset<pli> pq;
  //multiset<pli> pq_best_K;
  for (int i = 0; i < n; ++i) {
    //debug(i, VR[i], BP(i, 1));
    //VR[i] = BP(i, 1);
    pq.insert(mp(VR[i], i));
    /*pq_best_K.insert(mp(-VR[i], i));
    while (pq_best_K.size() > K) {
      pq_best_K.erase(pq_best_K.begin());
    }*/
  }
  for (int itr = 0; itr < K; ++itr) {
    ll f = pq.begin()->fi;
    int i = pq.begin()->se;
    pq.erase(pq.begin());
    /*{
      auto it = pq_best_K.find(mp(-f, i));
      if (it != pq_best_K.end()) {
        pq_best_K.erase(it);
      }
    }*/
    ans[itr] = f;
    if (need[i] < n - 1) {
      ++need[i];
      /*ll X = -pq_best_K.begin()->fi;
      if (!(pq_best_K.size() >= K - itr && Count(i, X - 1) - 1 < need[i])) {
        ll val = BP(i, need[i], f - 1);
        ++ask;
        pq.insert({val, i});
        pq_best_K.insert({-val, i});
        while (pq_best_K.size() > K - itr) {
          pq_best_K.erase(pq_best_K.begin());
        }
      }*/
      pq.insert({BP(i, need[i], f - 1), i});
    }
    /*while (pq_best_K.size() > K - itr) {
      pq_best_K.erase(pq_best_K.begin());
    }*/
  }
  debug(Time);
  debug(ask / 1e6);
  #ifndef DEBUG1
  for (int i = 0; i < K; i += 2) {
    cout << ans[i] << '\n';
  }
  #endif
    
  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")
      | 
road_construction.cpp: In function 'int32_t main()':
road_construction.cpp:46:22: warning: statement has no effect [-Wunused-value]
   46 |   #define debug(...) 1337
      |                      ^~~~
road_construction.cpp:349:3: note: in expansion of macro 'debug'
  349 |   debug(Time);
      |   ^~~~~
road_construction.cpp:46:22: warning: statement has no effect [-Wunused-value]
   46 |   #define debug(...) 1337
      |                      ^~~~
road_construction.cpp:440:3: note: in expansion of macro 'debug'
  440 |   debug(Time);
      |   ^~~~~
road_construction.cpp:46:22: warning: statement has no effect [-Wunused-value]
   46 |   #define debug(...) 1337
      |                      ^~~~
road_construction.cpp:441:3: note: in expansion of macro 'debug'
  441 |   debug(ask / 1e6);
      |   ^~~~~
road_construction.cpp:46:22: warning: statement has no effect [-Wunused-value]
   46 |   #define debug(...) 1337
      |                      ^~~~
road_construction.cpp:484:3: note: in expansion of macro 'debug'
  484 |   debug(Time);
      |   ^~~~~
road_construction.cpp:46:22: warning: statement has no effect [-Wunused-value]
   46 |   #define debug(...) 1337
      |                      ^~~~
road_construction.cpp:485:3: note: in expansion of macro 'debug'
  485 |   debug(ask / 1e6);
      |   ^~~~~

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