Submission #994350

#	Time	Username	Problem	Language	Result	Execution time	Memory
994350		awu	Train (APIO24_train)	C++17	40 / 100	1104 ms	92468 KiB

train

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

// #define int long long
#define ll long long
// #define double long double
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(x) do{auto __y = x; cerr << #x << " = " << __y << endl;}while(0)
using pii = pair<int, int>;
const ll inf = 1ll << 55;

// trains and meals are inc inc!!

vector<int> dcc;
struct range {
  int l, r;
};
struct segnode {
  int v, li, ri;
};
struct segtree {
  vector<vector<segnode>> t;
  void init(int s, vector<range> rs) {
    int n = 1;
    while(n < s) n *= 2;
    t.resize(n * 2);
    for(auto r : rs) {
      t[n + r.l].push_back({r.r, -1, -1});
    }
    for(int i = 0; i < n; i++) {
      sort(all(t[n + i]), [](segnode a, segnode b) {
        return a.v < b.v;
      });
    }
    for(int i = n - 1; i; i--) {
      int li = 0, ri = 0;
      while(li < t[i * 2].size() || ri < t[i * 2 + 1].size()) {
        if(ri == t[i * 2 + 1].size() || (li < t[i * 2].size() && t[i * 2][li].v <= t[i * 2 + 1][ri].v)) {
          t[i].push_back({t[i * 2][li].v, li, ri});
          li++;
        } else {
          t[i].push_back({t[i * 2 + 1][ri].v, li, ri});
          ri++;
        }
      }
    }
  }
  int query(int ql, int qr) {
    int lo = -1, hi = t[1].size();
    while(lo + 1 < hi) {
      int mid = (lo + hi) / 2;
      if(t[1][mid].v < qr) {
        lo = mid;
      } else {
        hi = mid;
      }
    }
    return query_helper(ql, qr, hi, 1, 0, t.size() / 2);
  }
  int query_helper(int ql, int qr, int i = -1, int n = 1, int tl = 0, int tr = -1) {
    int li, ri;
    if(i < t[n].size()) li = t[n][i].li, ri = t[n][i].ri;
    else li = t[n * 2].size(), ri = t[n * 2 + 1].size();
    int tm = (tl + tr) / 2;
    int res = 0;
    if(ql < tm) res += (ql <= tl && qr >= tm) ? li : query_helper(ql, qr, li, n * 2, tl, tm);
    if(qr > tm) res += (ql <= tm && qr >= tr) ? ri : query_helper(ql, qr, ri, n * 2 + 1, tm, tr);
    return res;
  }
};
segtree st;

struct my_hash {
  size_t operator()(int x) const {
    return x * 31;
  }
};

struct func {
  ll m, c;
  int lb;
  ll eval(int x) {
    return m * st.query(lb + 1, x) + c;
  }
};
struct lichao {
  int tl, tr;
  func f;
  lichao *lc, *rc;
  void insert(func g) {
    int tm = (tl + tr) / 2;
    if(f.eval(tm) > g.eval(tm)) swap(f, g);
    if(tl + 1 == tr) return;
    if(f.eval(tr - 1) >= g.eval(tr - 1)) {
      if(!rc) {
        rc = new lichao{tm, tr, g};
      } else {
        rc->insert(g);
      }
    } else if(f.eval(tl) >= g.eval(tl)) {
      if(!lc) {
        lc = new lichao{tl, tm, g};
      } else {
        lc->insert(g);
      }
    }
  }
  ll query(int x) {
    int tm = (tl + tr) / 2;
    ll res = f.eval(x);
    if(x < tm && lc) return min(res, lc->query(x));
    if(x >= tm && rc) return min(res, rc->query(x));
    return res;
  }
};

ll 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) {
  // #define int long long
  dcc.push_back(0);
  vector<range> meals;
  for(int i = 0; i < w; i++) {
    meals.push_back({l[i], r[i]});
    dcc.push_back(l[i]);
    dcc.push_back(r[i]);
  }
  sort(all(meals), [&](range a, range b) {
    return a.l < b.l;
  });
  struct edge {
    int x, y, a, b, c;
  };
  vector<edge> el;
  for(int i = 0; i < m; i++) {
    el.push_back({x[i], y[i], a[i], b[i], c[i]});
    dcc.push_back(a[i]);
    dcc.push_back(b[i]);
  }
  dcc.push_back(2e9);
  sort(all(el), [](edge a, edge b) {
    return a.a < b.a;
  });
  el.push_back({n - 1, n, (int)2e9, (int)2e9, 0});
  sort(all(dcc));
  dcc.erase(unique(all(dcc)), dcc.end());
  auto cc = [&](int x) {
    return lower_bound(all(dcc), x) - dcc.begin();
  };
  for(auto& meal : meals) {
    meal.l = cc(meal.l);
    meal.r = cc(meal.r);
  }
  st.init(dcc.size() + 5, meals);
  for(auto& e : el) {
    e.a = cc(e.a);
    e.b = cc(e.b);
  }
  vector<map<int, ll>> dp(n + 1); // arrivals only
  vector<lichao> lc(n + 1, {0, (int)dcc.size() + 5, {0, inf, 0}});
  vector<map<int, vector<func>>> todo(n + 1);
  dp[0][0] = 0;
  todo[0][0].push_back({t[0], 0, 0});
  for(auto [x, y, a, b, c] : el) {
    if(dp[x].empty() || dp[x].begin()->f > a) continue;
    if(!dp[y].count(b)) dp[y][b] = inf;
    while(todo[x].size() && todo[x].begin()->f <= a) {
      for(auto f : todo[x].begin()->s) {
        lc[x].insert(f);
      }
      todo[x].erase(todo[x].begin());
    }
    dp[y][b] = min(dp[y][b], lc[x].query(a) + c);
    if(y < n) todo[y][b].push_back({t[y], dp[y][b], b});
    // cerr << "dp[" << y << "][" << dcc[b] << "] = " << dp[y][b] << endl;
  }
  if(!dp[n].count(dcc.size() - 1)) return -1;
  return dp[n][dcc.size() - 1];
}

Compilation message (stderr)

train.cpp: In member function 'void segtree::init(int, std::vector<range>)':
train.cpp:43:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segnode>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |       while(li < t[i * 2].size() || ri < t[i * 2 + 1].size()) {
      |             ~~~^~~~~~~~~~~~~~~~~
train.cpp:43:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segnode>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |       while(li < t[i * 2].size() || ri < t[i * 2 + 1].size()) {
      |                                     ~~~^~~~~~~~~~~~~~~~~~~~~
train.cpp:44:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segnode>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         if(ri == t[i * 2 + 1].size() || (li < t[i * 2].size() && t[i * 2][li].v <= t[i * 2 + 1][ri].v)) {
      |            ~~~^~~~~~~~~~~~~~~~~~~~~~
train.cpp:44:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segnode>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         if(ri == t[i * 2 + 1].size() || (li < t[i * 2].size() && t[i * 2][li].v <= t[i * 2 + 1][ri].v)) {
      |                                          ~~~^~~~~~~~~~~~~~~~~
train.cpp: In member function 'int segtree::query_helper(int, int, int, int, int, int)':
train.cpp:68:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segnode>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     if(i < t[n].size()) li = t[n][i].li, ri = t[n][i].ri;
      |        ~~^~~~~~~~~~~~~

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