oj.uz

Submission #1009766

# Submission time Handle Problem Language Result Execution time Memory
1009766 2024-06-28T03:53:14 Z rxlfd314 Train (APIO24_train) C++17
100 / 100
 814 ms 178888 KB 
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using arl2 = array<ll, 2>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

constexpr int mxN = 100005;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;

struct Node {
  int val;
  Node *lft, *rht;
  Node(int v) : val(v), lft(nullptr), rht(nullptr) {}
  Node(Node *l, Node *r) : val(l->val + r->val), lft(l), rht(r) {}
  Node(Node *n) : val(n->val), lft(n->lft), rht(n->rht) {}
};

vt<int> cmp_l, cmp_r;

Node *sts[mxN<<1];

Node *build(int tl = 0, int tr = size(cmp_r)-1) {
  if (tl == tr)
    return new Node(0);
  int tm = tl + tr >> 1;
  return new Node(build(tl, tm), build(tm+1, tr));
}

Node *update(Node *n, int p, int v, int tl = 0, int tr = size(cmp_r)-1) {
  if (tl == tr)
    return new Node(n->val + v);
  int tm = tl + tr >> 1;
  if (p <= tm)
    return new Node(update(n->lft, p, v, tl, tm), n->rht);
  return new Node(n->lft, update(n->rht, p, v, tm+1, tr));
}

int query(Node *n, int ql, int qr, int tl = 0, int tr = size(cmp_r)-1) {
  if (tl > qr || tr < ql)
    return 0;
  if (ql <= tl && tr <= qr)
    return n->val;
  int tm = tl + tr >> 1;
  return query(n->lft, ql, qr, tl, tm) + query(n->rht, ql, qr, tm+1, tr);
}

struct Line {
  int l, m;
  ll c;
  ll eval(int x) {
    return 1ll * m * query(sts[l], 0, x) + c;
  }
};

struct Lichao {
  Line line;
  Lichao *lft, *rht;
  void update(Line new_line, int tl = 0, int tr = size(cmp_r)-1) {
    int tm = tl + tr >> 1;
    if (make_pair(new_line.eval(tm), -new_line.l) < make_pair(line.eval(tm), -line.l))
      swap(new_line, line);
    if (tl == tr)
      return;
    if (new_line.eval(tl) < line.eval(tl)) {
      if (!lft) {
        lft = new Lichao();
        lft->line = {0, 0, LLONG_MAX};
        lft->lft = lft->rht = nullptr;
      }
      lft->update(new_line, tl, tm);
    } else {
      if (!rht) {
        rht = new Lichao();
        rht->line = {0, 0, LLONG_MAX};
        rht->lft = rht->rht = nullptr;
      }
      rht->update(new_line, tm+1, tr);
    }
  }
  ll query(int x, int tl = 0, int tr = size(cmp_r)-1) {
    ll ret = line.eval(x);
    int tm = tl + tr >> 1;
    if (x <= tm)
      return min(ret, lft ? lft->query(x, tl, tm) : ret);
    return min(ret, rht ? rht->query(x, tm+1, tr) : ret);
  }
};

vt<ari2> adj[mxN*2];
vt<int> ins[mxN*2];
int node[mxN*2], times[mxN*2], ord[mxN*2];
Lichao *lcts[mxN];
ll dp[mxN*2];

ll solve(int N, int M, int W, vt<int> T, vt<int> X, vt<int> Y,
                              vt<int> A, vt<int> B, vt<int> C, vt<int> L, vt<int> R) {
  map<ari2, int> ind;
  ind[{0, 0}] = 0;
  FOR(i, 0, M-1) {
    int x = X[i], y = Y[i], a = A[i], b = B[i];
    if (ind.find({x, a}) == end(ind))
      ind[{x, a}] = size(ind);
    if (ind.find({y, b}) == end(ind))
      ind[{y, b}] = size(ind);
  }
  
  const int K = size(ind);
  FOR(i, 0, M-1) {
    int a = ind[{X[i], A[i]}];
    int b = ind[{Y[i], B[i]}];
    node[a] = X[i], times[a] = A[i];
    node[b] = Y[i], times[b] = B[i];
    adj[a].push_back({b, C[i]});
  }
  
  {
    cmp_l.push_back(0);
    cmp_r.push_back(0);
    FOR(i, 0, W-1) {
      cmp_l.push_back(L[i]);
      cmp_r.push_back(R[i]);
    }
    
    sort(all(cmp_l));
    cmp_l.erase(unique(all(cmp_l)), end(cmp_l));
    sort(all(cmp_r));
    cmp_r.erase(unique(all(cmp_r)), end(cmp_r));
    
    FOR(i, 0, W-1) {
      ins[lower_bound(all(cmp_l), L[i]) - begin(cmp_l)].push_back(lower_bound(all(cmp_r), R[i]) - begin(cmp_r));
    }
    sts[size(cmp_l)] = build();
    ROF(i, size(cmp_l)-1, 0) {
      sts[i] = new Node(sts[i+1]);
      for (int j : ins[i])
        sts[i] = update(sts[i], j, 1);
    }
  }
  
  iota(ord, ord+K, 0);
  sort(ord, ord+K, [&](const int &a, const int &b) {
    return times[a] < times[b];    
  });
  
  memset(dp, 0x3f, K<<3);
  FOR(i, 0, N-1) {
    lcts[i] = new Lichao();
    lcts[i]->line = {0, 0, LLONG_MAX};
    lcts[i]->lft = lcts[i]->rht = nullptr;
  }
  dp[0] = 0;
  ll ans = INF;
  for (int i : ord) {
    ll go = lcts[node[i]]->query(lower_bound(all(cmp_r), times[i]) - begin(cmp_r) - 1);
    if (min(go, dp[i]) < INF)
      for (auto [j, v] : adj[i])
        dp[j] = min(dp[j], min(go, dp[i]) + v);
    int j = upper_bound(all(cmp_l), times[i]) - begin(cmp_l);
    if (dp[i] < INF)
      lcts[node[i]]->update({j, T[node[i]], dp[i]});
    if (node[i] == N-1 && dp[i] < INF)
      ans = min(ans, dp[i] + 1ll * T[node[i]] * (j < size(cmp_l) ? sts[j]->val : 0));
  }
  
  return ans < INF ? ans : -1;
}

Compilation message

train.cpp: In function 'Node* build(int, int)':
train.cpp:36:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
train.cpp: In function 'Node* update(Node*, int, int, int, int)':
train.cpp:43:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
train.cpp: In function 'int query(Node*, int, int, int, int)':
train.cpp:54:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
train.cpp: In member function 'void Lichao::update(Line, int, int)':
train.cpp:70:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
train.cpp: In member function 'll Lichao::query(int, int, int)':
train.cpp:93:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |     int tm = tl + tr >> 1;
      |              ~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 10108 KB Correct.
2 Correct 36 ms 10076 KB Correct.
3 Correct 38 ms 10076 KB Correct.
4 Correct 39 ms 10100 KB Correct.
5 Correct 8 ms 9820 KB Correct.
6 Correct 21 ms 9876 KB Correct.
7 Correct 12 ms 9820 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 37716 KB Correct.
2 Correct 188 ms 44372 KB Correct.
3 Correct 8 ms 9820 KB Correct.
4 Correct 16 ms 16656 KB Correct.
5 Correct 8 ms 9820 KB Correct.
6 Correct 157 ms 36920 KB Correct.
7 Correct 8 ms 9816 KB Correct.
8 Correct 144 ms 43060 KB Correct.
9 Correct 183 ms 44368 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 37716 KB Correct.
2 Correct 188 ms 44372 KB Correct.
3 Correct 8 ms 9820 KB Correct.
4 Correct 16 ms 16656 KB Correct.
5 Correct 8 ms 9820 KB Correct.
6 Correct 157 ms 36920 KB Correct.
7 Correct 8 ms 9816 KB Correct.
8 Correct 144 ms 43060 KB Correct.
9 Correct 183 ms 44368 KB Correct.
10 Correct 635 ms 138952 KB Correct.
11 Correct 677 ms 175392 KB Correct.
12 Correct 22 ms 16472 KB Correct.
13 Correct 8 ms 9820 KB Correct.
14 Correct 673 ms 111304 KB Correct.
15 Correct 688 ms 177200 KB Correct.
16 Correct 742 ms 114928 KB Correct.
17 Correct 560 ms 118812 KB Correct.

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 10108 KB Correct.
2 Correct 36 ms 10076 KB Correct.
3 Correct 38 ms 10076 KB Correct.
4 Correct 39 ms 10100 KB Correct.
5 Correct 8 ms 9820 KB Correct.
6 Correct 21 ms 9876 KB Correct.
7 Correct 12 ms 9820 KB Correct.
8 Correct 175 ms 37716 KB Correct.
9 Correct 188 ms 44372 KB Correct.
10 Correct 8 ms 9820 KB Correct.
11 Correct 16 ms 16656 KB Correct.
12 Correct 8 ms 9820 KB Correct.
13 Correct 157 ms 36920 KB Correct.
14 Correct 8 ms 9816 KB Correct.
15 Correct 144 ms 43060 KB Correct.
16 Correct 183 ms 44368 KB Correct.
17 Correct 635 ms 138952 KB Correct.
18 Correct 677 ms 175392 KB Correct.
19 Correct 22 ms 16472 KB Correct.
20 Correct 8 ms 9820 KB Correct.
21 Correct 673 ms 111304 KB Correct.
22 Correct 688 ms 177200 KB Correct.
23 Correct 742 ms 114928 KB Correct.
24 Correct 560 ms 118812 KB Correct.
25 Correct 737 ms 176672 KB Correct.
26 Correct 805 ms 177556 KB Correct.
27 Correct 698 ms 178584 KB Correct.
28 Correct 712 ms 178888 KB Correct.
29 Correct 774 ms 140484 KB Correct.
30 Correct 799 ms 122644 KB Correct.
31 Correct 793 ms 122312 KB Correct.
32 Correct 814 ms 122132 KB Correct.
33 Correct 729 ms 112672 KB Correct.
34 Correct 710 ms 113052 KB Correct.
35 Correct 753 ms 116076 KB Correct.
36 Correct 745 ms 122804 KB Correct.
37 Correct 728 ms 178404 KB Correct.
38 Correct 806 ms 117792 KB Correct.
39 Correct 699 ms 111252 KB Correct.
40 Correct 725 ms 178116 KB Correct.
41 Correct 314 ms 100904 KB Correct.
42 Correct 303 ms 95656 KB Correct.
43 Correct 652 ms 100180 KB Correct.
44 Correct 716 ms 178504 KB Correct.
45 Correct 739 ms 178064 KB Correct.
46 Correct 659 ms 174788 KB Correct.
47 Correct 157 ms 62240 KB Correct.
48 Correct 158 ms 59076 KB Correct.
49 Correct 157 ms 58820 KB Correct.
50 Correct 163 ms 58312 KB Correct.
51 Correct 174 ms 57640 KB Correct.
52 Correct 161 ms 58268 KB Correct.