Submission #1009766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009766		rxlfd314	Train (APIO24_train)	C++17	100 / 100	814 ms	178888 KiB

train

#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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60