oj.uz

Submission #395642

# Submission time Handle Problem Language Result Execution time Memory
395642 2021-04-28T17:34:17 Z usachevd0 Road Construction (JOI21_road_construction) C++14
5 / 100
 1633 ms 539384 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;
}

#define int ll

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 = 1e7 + 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;
}

int ans[2 * maxN];

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<int, 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 + X[i] - 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 + X[i] + Y[i], mp(i, 1)));
      }
    }
  }
  for (int e = 0; e < K; ++e) {
    ans[e] = pq.begin()->fi;
    cout << ans[e] << '\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(res.fi + X[i] - 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(res.fi + X[i] + Y[i], mp(i, 1)));
      }
    }
  }
  
    
  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")
      |

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 70376 KB Output is correct
2 Correct 374 ms 70384 KB Output is correct
3 Correct 323 ms 67384 KB Output is correct
4 Correct 307 ms 67268 KB Output is correct
5 Correct 349 ms 69408 KB Output is correct
6 Correct 5 ms 2124 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 1103 ms 537404 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1200 ms 539384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1200 ms 539384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 70376 KB Output is correct
2 Correct 374 ms 70384 KB Output is correct
3 Correct 323 ms 67384 KB Output is correct
4 Correct 307 ms 67268 KB Output is correct
5 Correct 349 ms 69408 KB Output is correct
6 Correct 5 ms 2124 KB Output is correct
7 Runtime error 1633 ms 520772 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 70376 KB Output is correct
2 Correct 374 ms 70384 KB Output is correct
3 Correct 323 ms 67384 KB Output is correct
4 Correct 307 ms 67268 KB Output is correct
5 Correct 349 ms 69408 KB Output is correct
6 Correct 5 ms 2124 KB Output is correct
7 Runtime error 1103 ms 537404 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -