oj.uz

Submission #395613

# Submission time Handle Problem Language Result Execution time Memory
395613 2021-04-28T16:47:27 Z usachevd0 Road Construction (JOI21_road_construction) C++17
32 / 100
 10000 ms 109984 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3511 ms 14160 KB Output is correct
2 Correct 3453 ms 14216 KB Output is correct
3 Correct 3263 ms 14084 KB Output is correct
4 Correct 3176 ms 14048 KB Output is correct
5 Correct 2115 ms 12968 KB Output is correct
6 Correct 21 ms 7632 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10014 ms 109756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9175 ms 109860 KB Output is correct
2 Correct 9111 ms 109956 KB Output is correct
3 Correct 7 ms 7244 KB Output is correct
4 Correct 4875 ms 107836 KB Output is correct
5 Correct 5482 ms 86816 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9175 ms 109860 KB Output is correct
2 Correct 9111 ms 109956 KB Output is correct
3 Correct 7 ms 7244 KB Output is correct
4 Correct 4875 ms 107836 KB Output is correct
5 Correct 5482 ms 86816 KB Output is correct
6 Correct 9098 ms 109924 KB Output is correct
7 Correct 8983 ms 109984 KB Output is correct
8 Correct 6 ms 7236 KB Output is correct
9 Correct 6 ms 7244 KB Output is correct
10 Correct 8938 ms 109720 KB Output is correct
11 Correct 5293 ms 107832 KB Output is correct
12 Correct 5669 ms 86756 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3511 ms 14160 KB Output is correct
2 Correct 3453 ms 14216 KB Output is correct
3 Correct 3263 ms 14084 KB Output is correct
4 Correct 3176 ms 14048 KB Output is correct
5 Correct 2115 ms 12968 KB Output is correct
6 Correct 21 ms 7632 KB Output is correct
7 Execution timed out 10048 ms 49020 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3511 ms 14160 KB Output is correct
2 Correct 3453 ms 14216 KB Output is correct
3 Correct 3263 ms 14084 KB Output is correct
4 Correct 3176 ms 14048 KB Output is correct
5 Correct 2115 ms 12968 KB Output is correct
6 Correct 21 ms 7632 KB Output is correct
7 Execution timed out 10014 ms 109756 KB Time limit exceeded
8 Halted 0 ms 0 KB -