oj.uz

Submission #994350

# Submission time Handle Problem Language Result Execution time Memory
994350 2024-06-07T12:57:51 Z awu Train (APIO24_train) C++17
40 / 100
 1000 ms 92468 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Correct.
2 Correct 1 ms 604 KB Correct.
3 Correct 1 ms 348 KB Correct.
4 Correct 1 ms 604 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 27352 KB Correct.
2 Correct 206 ms 40224 KB Correct.
3 Correct 1 ms 344 KB Correct.
4 Correct 11 ms 15196 KB Correct.
5 Correct 0 ms 344 KB Correct.
6 Correct 200 ms 26272 KB Correct.
7 Correct 1 ms 344 KB Correct.
8 Correct 201 ms 40100 KB Correct.
9 Correct 230 ms 40484 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 27352 KB Correct.
2 Correct 206 ms 40224 KB Correct.
3 Correct 1 ms 344 KB Correct.
4 Correct 11 ms 15196 KB Correct.
5 Correct 0 ms 344 KB Correct.
6 Correct 200 ms 26272 KB Correct.
7 Correct 1 ms 344 KB Correct.
8 Correct 201 ms 40100 KB Correct.
9 Correct 230 ms 40484 KB Correct.
10 Correct 398 ms 79924 KB Correct.
11 Correct 371 ms 91700 KB Correct.
12 Correct 11 ms 15192 KB Correct.
13 Correct 1 ms 348 KB Correct.
14 Correct 685 ms 75864 KB Correct.
15 Correct 385 ms 91696 KB Correct.
16 Correct 633 ms 76592 KB Correct.
17 Correct 720 ms 91700 KB Correct.

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Correct.
2 Correct 1 ms 604 KB Correct.
3 Correct 1 ms 348 KB Correct.
4 Correct 1 ms 604 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 194 ms 27352 KB Correct.
9 Correct 206 ms 40224 KB Correct.
10 Correct 1 ms 344 KB Correct.
11 Correct 11 ms 15196 KB Correct.
12 Correct 0 ms 344 KB Correct.
13 Correct 200 ms 26272 KB Correct.
14 Correct 1 ms 344 KB Correct.
15 Correct 201 ms 40100 KB Correct.
16 Correct 230 ms 40484 KB Correct.
17 Correct 398 ms 79924 KB Correct.
18 Correct 371 ms 91700 KB Correct.
19 Correct 11 ms 15192 KB Correct.
20 Correct 1 ms 348 KB Correct.
21 Correct 685 ms 75864 KB Correct.
22 Correct 385 ms 91696 KB Correct.
23 Correct 633 ms 76592 KB Correct.
24 Correct 720 ms 91700 KB Correct.
25 Correct 395 ms 91868 KB Correct.
26 Correct 401 ms 92208 KB Correct.
27 Correct 411 ms 92208 KB Correct.
28 Correct 417 ms 92360 KB Correct.
29 Correct 460 ms 79924 KB Correct.
30 Correct 581 ms 78304 KB Correct.
31 Correct 576 ms 76516 KB Correct.
32 Correct 578 ms 77284 KB Correct.
33 Correct 744 ms 76928 KB Correct.
34 Correct 772 ms 77360 KB Correct.
35 Correct 987 ms 78640 KB Correct.
36 Correct 561 ms 78044 KB Correct.
37 Correct 399 ms 92468 KB Correct.
38 Correct 657 ms 78052 KB Correct.
39 Correct 746 ms 76596 KB Correct.
40 Correct 400 ms 92208 KB Correct.
41 Correct 148 ms 55188 KB Correct.
42 Correct 141 ms 40668 KB Correct.
43 Correct 324 ms 44000 KB Correct.
44 Correct 405 ms 92120 KB Correct.
45 Correct 409 ms 91952 KB Correct.
46 Correct 386 ms 91700 KB Correct.
47 Execution timed out 1104 ms 79408 KB Time limit exceeded
48 Halted 0 ms 0 KB -