Submission #1127700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127700		juicy	Train (APIO24_train)	C++20	10 / 100	609 ms	255256 KiB

train

#include <bits/stdc++.h>

#include "train.h"

using namespace std;

#define             fi  first
#define             se  second
#define           left  ___left___
#define          right  ___right___
#define   scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define  print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define     file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#ifdef LOCAL
  #include "debug.h"
#else
  #define debug(...) 42
#endif

namespace std {
template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream &print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class...U> print_op(tuple <U...>) { return print_tuple_utils<0, tuple <U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))>typename enable_if <!is_same<Con, string>::value, ostream &>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class T> print_op(stack <T>) { vector <T> v; stack <T> st = u; while (!st.empty()) v.push_back(st.top()), st.pop(); reverse(v.begin(), v.end()); return out << v; }
template <class T> print_op(queue <T>) { queue <T> q = u; out << '{'; while (!q.empty()) { out << q.front(); q.pop(); if (!q.empty()) out << ", "; } out << '}'; return out; }
template <class T, class X, class Y> print_op(priority_queue <T, X, Y>) { priority_queue <T, X, Y> pq = u; out << '{'; while (!pq.empty()) { out << pq.top(); pq.pop(); if (!pq.empty()) out << ", "; } out << '}'; return out; }
}

template <class A, class B> bool minimize(A &a, B b)  { return a > b ? a = b, true : false; }
template <class A, class B> bool maximize(A &a, B b)  { return a < b ? a = b, true : false; }

const int MAX = 1e5 + 5, BL = 320, SZ = MAX / BL + 3;
const long long INF = 1e18;

int bk[MAX], lt[SZ], rt[SZ], cnt[MAX], lz[SZ], col[MAX];
long long Min[SZ][MAX], cost[MAX], val[MAX], dp[MAX];

void upd(int id) {
  for (int i = lt[id]; i <= rt[id]; ++i) {
    Min[id][col[i]] = INF;
    cnt[i] += lz[id];
  }
  for (int i = lt[id]; i <= rt[id]; ++i) {
    Min[id][col[i]] = min(Min[id][col[i]], cnt[i] * val[i] + cost[i]);
  }
  lz[id] = 0;
}

void add(int i) {
  if (i < 0) {
    return;
  }
  int id = bk[i];
  for (int j = i; j >= lt[id]; --j) {
    ++cnt[j];
  }
  upd(id);
  for (int j = id - 1; ~j; --j) {
    ++lz[j];
  }
}

long long qry(int i, int ind, int T) {
  if (i < 0) {
    return INF;
  }
  int id = bk[i];
  long long res = INF;
  for (int j = i; j >= lt[id]; --j) {
    if (col[j] == ind) {
      res = min(res, 1LL * (cnt[j] + lz[id]) * T + cost[j]);
    }
  }
  for (int j = id - 1; j >= 0; --j) {
    res = min(res, Min[j][ind] + lz[j] * T);
  }
  return res;
}

template<class T>
int lwb(const vector<T> &v, const T &x) {
  return lower_bound(v.begin(), v.end(), x) - v.begin();
}

template<class T>
int upb(const vector<T> &v, const T &x) {
  return upper_bound(v.begin(), v.end(), x) - v.begin();
}

long long solve(int N, int M, int W, vector<int> T, vector<int> X, vector<int> Y, vector<int> A, vector<int> B, vector<int> C, vector<int> L, vector<int> R) {
  for (int i = 0; i < M; ++i) {
    bk[i] = i / BL;
    rt[bk[i]] = i;
  }
  for (int i = M - 1; ~i; --i) {
    lt[bk[i]] = i;
  }
  for (int i = 0; i <= bk[M - 1]; ++i) {
    for (int j = 0; j < N; ++j) {
      Min[i][j] = INF;
    }
  }
  vector<int> ordB(M);
  iota(ordB.begin(), ordB.end(), 0);
  sort(ordB.begin(), ordB.end(), [&](int u, int v) {
    return B[u] < B[v];
  });
  for (int i = 0; i < M; ++i) {
    col[i] = Y[ordB[i]];
    val[i] = T[col[i]];
    cost[i] = INF;
  }
  auto BB = B;
  sort(BB.begin(), BB.end());
  vector<int> ordA(M);
  iota(ordA.begin(), ordA.end(), 0);
  sort(ordA.begin(), ordA.end(), [&](int u, int v) {
    return A[u] < A[v];
  });
  vector<int> posB(M);
  for (int i = 0; i < M; ++i) {
    posB[ordB[i]] = i;
  }
  vector<int> ordW(W);
  iota(ordW.begin(), ordW.end(), 0);
  sort(ordW.begin(), ordW.end(), [&](int u, int v) {
    return R[u] < R[v];
  });
  int j = 0;
  for (int id : ordA) {
    dp[id] = INF;
    while (j < W && R[ordW[j]] < A[id]) {
      int id = ordW[j++];
      add(lwb(BB, L[id]) - 1);
    }
    if (X[id] == 0) {
      minimize(dp[id], j * T[0]);
    }
    minimize(dp[id], qry(upb(BB, A[id]) - 1, X[id], T[X[id]]));
    dp[id] = min(INF, dp[id] + C[id]);
    cost[posB[id]] = dp[id]; 
    upd(bk[posB[id]]);
  }
  while (j < W) {
    int id = ordW[j++];
    add(lwb(BB, L[id]) - 1);
  }
  long long res = qry(M - 1, N - 1, T[N - 1]);
	return res == INF ? -1 : res;
}

// signed main() {
//   file("TRAIN");
//   int N, M, W;
//   assert(3 == scanf("%d %d %d", &N, &M, &W));
//   std::vector<int> t(N);
//   std::vector<int> x(M);
//   std::vector<int> y(M);
//   std::vector<int> a(M);
//   std::vector<int> b(M);
//   std::vector<int> c(M);
//   std::vector<int> l(W);
//   std::vector<int> r(W);
//   for (int i = 0; i < N; i++)
//     assert(1 == scanf("%d", &t[i]));
//   for (int i = 0; i < M; i++)
//     assert(5 == scanf("%d %d %d %d %d", &x[i], &y[i], &a[i], &b[i], &c[i]));
//   for (int i = 0; i < W; i++)
//     assert(2 == scanf("%d %d", &l[i], &r[i]));
//   printf("%lld", solve(N, M, W, t, x, y, a, b, c, l, r));
// }

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60