oj.uz

답안 #395644

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
395644 2021-04-28T17:34:54 Z usachevd0 Road Construction (JOI21_road_construction) C++17
59 / 100
 2988 ms 963040 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 = 2e7 + 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

# 결과 실행 시간 메모리 Grader output
1 Correct 435 ms 70376 KB Output is correct
2 Correct 412 ms 70368 KB Output is correct
3 Correct 387 ms 67360 KB Output is correct
4 Correct 363 ms 67216 KB Output is correct
5 Correct 385 ms 69372 KB Output is correct
6 Correct 6 ms 2252 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2988 ms 963040 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1939 ms 497496 KB Output is correct
2 Correct 1947 ms 497588 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1775 ms 495236 KB Output is correct
5 Correct 1723 ms 497760 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1939 ms 497496 KB Output is correct
2 Correct 1947 ms 497588 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1775 ms 495236 KB Output is correct
5 Correct 1723 ms 497760 KB Output is correct
6 Correct 1904 ms 497544 KB Output is correct
7 Correct 1933 ms 497384 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1907 ms 497292 KB Output is correct
11 Correct 1736 ms 495300 KB Output is correct
12 Correct 1738 ms 497640 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 435 ms 70376 KB Output is correct
2 Correct 412 ms 70368 KB Output is correct
3 Correct 387 ms 67360 KB Output is correct
4 Correct 363 ms 67216 KB Output is correct
5 Correct 385 ms 69372 KB Output is correct
6 Correct 6 ms 2252 KB Output is correct
7 Correct 1803 ms 295144 KB Output is correct
8 Correct 1802 ms 295136 KB Output is correct
9 Correct 353 ms 67516 KB Output is correct
10 Correct 1135 ms 294520 KB Output is correct
11 Correct 1402 ms 294296 KB Output is correct
12 Correct 1176 ms 294692 KB Output is correct
13 Correct 1331 ms 293688 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 435 ms 70376 KB Output is correct
2 Correct 412 ms 70368 KB Output is correct
3 Correct 387 ms 67360 KB Output is correct
4 Correct 363 ms 67216 KB Output is correct
5 Correct 385 ms 69372 KB Output is correct
6 Correct 6 ms 2252 KB Output is correct
7 Runtime error 2988 ms 963040 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -