Submission #1047226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047226		avighna	Toll (BOI17_toll)	C++17	7 / 100	44 ms	33116 KiB

toll

#include <bits/stdc++.h>

typedef long long ll;

const ll inf = 1e15;
const ll N = 50001;
const ll K = 5;

ll adj[N][K];

ll k;

struct Node {
  std::vector<std::vector<ll>> arr;
  ll tl = -1, tr = -1;

  Node() {}
};

bool operator==(const Node &a, const Node &b) { return a.arr == b.arr; }

class SegmentTree {
public:
  std::vector<Node> seg;
  ll n;

  SegmentTree(ll n) {
    this->n = n;
    seg.resize(4 * n);
  }

  Node idt() { return Node(); }
  Node f(const Node &a, const Node &b) {
    if (a == idt()) {
      return b;
    }
    if (b == idt()) {
      return a;
    }

    Node ret;
    ret.tl = a.tl, ret.tr = b.tr;
    auto &ans = ret.arr;
    ans = std::vector<std::vector<ll>>(k, std::vector<ll>(k, inf));
    for (ll s = 0; s < k; ++s) {
      for (ll e = 0; e < k; ++e) {
        for (ll s1 = 0; s1 < k; ++s1) {
          for (ll e1 = 0; e1 < k; ++e1) {
            ans[s][e] =
                std::min(ans[s][e],
                         a.arr[s][s1] + adj[k * a.tr + s1][e1] + b.arr[e1][e]);
          }
        }
      }
    }
    return ret;
  }

  void construct(ll v, ll tl, ll tr) {
    if (tl == tr) {
      seg[v] = Node();
      seg[v].tl = tl, seg[v].tr = tr;
      seg[v].arr = std::vector<std::vector<ll>>(k, std::vector<ll>(k, inf));
      for (ll i = 0; i < k; ++i) {
        seg[v].arr[i][i] = 0;
      }
    } else {
      ll tm = (tl + tr) / 2;
      construct(2 * v, tl, tm);
      construct(2 * v + 1, tm + 1, tr);
      seg[v] = f(seg[2 * v], seg[2 * v + 1]);
    }
  }
  void construct() { construct(1, 0, n); }

  Node query(ll v, ll tl, ll tr, ll l, ll r) {
    if (tl > tr || l > r || tr < l || r < tl) {
      return idt();
    }
    if (l <= tl && tr <= r) {
      return seg[v];
    }
    ll tm = (tl + tr) / 2;
    return f(query(2 * v, tl, tm, l, r), query(2 * v + 1, tm + 1, tr, l, r));
  }
  Node query(ll l, ll r) { return query(1, 0, n, l, r); }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  ll n, m, o;
  std::cin >> k >> n >> m >> o;

  for (ll i = 0; i < n; ++i) {
    for (ll j = 0; j < k; ++j) {
      adj[i][j] = inf;
    }
  }
  for (ll i = 0, a, b, t; i < m; ++i) {
    std::cin >> a >> b >> t;
    adj[a][b - a - (k - (a % k))] = t;
  }

  SegmentTree tree(n);
  tree.construct();
  while (o--) {
    ll a, b;
    std::cin >> a >> b;
    auto q = tree.query(a / k, b / k);
    ll ans = q.arr[a % k][b % k];
    std::cout << (ans == inf ? -1 : ans) << '\n';
  }
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44