oj.uz

Submission #995818

# Submission time Handle Problem Language Result Execution time Memory
995818 2024-06-09T23:42:56 Z MilosMilutinovic Train (APIO24_train) C++17
5 / 100
 1000 ms 29520 KB 
#include "train.h"
#include <bits/stdc++.h>

using namespace std;

const int BLOCK = 333;

const int N = 100005;
const int MAX = 300 * N;

const long long inf = (long long) 1e18;

int root[N], tsz, ch[MAX][2];
long long mn[MAX], tag[MAX];

void push(int x) {
  if (!x || !tag[x]) {
    return;
  }
  if (!ch[x][0]) {
    ch[x][0] = ++tsz;
    mn[ch[x][0]] = inf;
  }
  if (!ch[x][1]) {
    ch[x][1] = ++tsz;
    mn[ch[x][1]] = inf;
  }
  mn[ch[x][0]] += tag[x];
  mn[ch[x][1]] += tag[x];
  tag[ch[x][0]] += tag[x];
  tag[ch[x][1]] += tag[x];
  tag[x] = 0;
}

void pull(int x) {
  mn[x] = inf;
  if (ch[x][0]) {
    mn[x] = min(mn[x], mn[ch[x][0]]);
  }
  if (ch[x][1]) {
    mn[x] = min(mn[x], mn[ch[x][1]]);
  }
}

void AddRange(int& x, int l, int r, int ll, int rr, int v) {
  if (ll > rr) {
    return;
  }
  if (!x) {
    x = ++tsz;
    mn[x] = inf;
  }
  if (ll <= l && r <= rr) {
    tag[x] += v;
    mn[x] += v;
    push(x);
    return;
  }
  push(x);
  int mid = (l + r) >> 1;
  if (rr <= mid) {
    AddRange(ch[x][0], l, mid, ll, rr, v);
  } else if (ll > mid) {
    AddRange(ch[x][1], mid + 1, r, ll, rr, v);
  } else {
    AddRange(ch[x][0], l, mid, ll, rr, v);
    AddRange(ch[x][1], mid + 1, r, ll, rr, v);
  }
  pull(x);
}

void Modify(int& x, int l, int r, int i, long long v) {
  if (!x) {
    x = ++tsz;
    mn[x] = inf;
  }
  if (l == r) {
    mn[x] = min(mn[x], v);
    return;
  }
  push(x);
  int mid = (l + r) >> 1;
  if (i <= mid) {
    Modify(ch[x][0], l, mid, i, v);
  } else {
    Modify(ch[x][1], mid + 1, r, i, v);
  }
  pull(x);
}

long long Query(int v, int l, int r, int ll, int rr) {
  if (!v) {
    return inf;
  }
  if (ll <= l && r <= rr) {
    return mn[v];
  }
  push(v);
  int mid = (l + r) >> 1;
  long long ret = inf;
  if (rr <= mid) {
    ret = Query(ch[v][0], l, mid, ll, rr);
  } else if (ll > mid) {
    ret = Query(ch[v][1], mid + 1, r, ll, rr);
  } else {
    ret = min(Query(ch[v][0], l, mid, ll, rr), Query(ch[v][1], mid + 1, r, ll, rr));
  }
  pull(v);
  return ret;
}

template <typename T>
class fenwick {
 public:
  vector<T> fenw;
  int n;

  fenwick(int _n) : n(_n) {
    fenw.resize(n);
  }

  void modify(int x, T v) {
    while (x < n) {
      fenw[x] += v;
      x |= (x + 1);
    }
  }

  T get(int x) {
    T v{};
    while (x >= 0) {
      v += fenw[x];
      x = (x & (x + 1)) - 1;
    }
    return v;
  }
};

long long solve(int n, int m, int w, std::vector<int> T, std::vector<int> X, std::vector<int> Y,
                std::vector<int> A, std::vector<int> B, std::vector<int> C, std::vector<int> L,
                std::vector<int> R) {
  vector<vector<int>> my(n);
  for (int i = 0; i < m; i++) {
    my[X[i]].push_back(A[i]);
    my[Y[i]].push_back(B[i]);
  }
  my[0].push_back(0);
  vector<int> sz(n);
  for (int i = 0; i < n; i++) {
    sort(my[i].begin(), my[i].end());
    if (!my[i].empty()) {
      my[i].erase(unique(my[i].begin(), my[i].end()), my[i].end());
    }
    sz[i] = (int) my[i].size();
  }
  vector<pair<int, int>> vec;
  for (int i = 0; i < n; i++) {
    for (int j : my[i]) {
      vec.emplace_back(i, j);
    }
  }
  sort(vec.begin(), vec.end(), [&](pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
  });
  vector<vector<long long>> dist(n);
  for (int i = 0; i < n; i++) {
    dist[i].resize(sz[i], inf);
  }
  dist[0][0] = 0;
  auto Count = [&](int from, int to) {
    int total = 0;
    for (int i = 0; i < w; i++) {
      if (from <= L[i] && R[i] <= to) {
        total += 1;
      }
    }
    return total;
  };
  vector<int> xs;
  for (int i = 0; i < w; i++) {
    xs.push_back(L[i]);
    xs.push_back(R[i]);
  }
  for (int i = 0; i < n; i++) {
    for (int j : my[i]) {
      xs.push_back(j);
    }
  }
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  vector<vector<vector<int>>> g(n);
  for (int i = 0; i < n; i++) {
    g[i].resize(sz[i]);
  }
  for (int i = 0; i < m; i++) {
    int idx = (int) (lower_bound(my[X[i]].begin(), my[X[i]].end(), A[i]) - my[X[i]].begin());
    g[X[i]][idx].push_back(i);
  }
  vector<array<int, 2>> segs;
  for (int i = 0; i < w; i++) {
    segs.push_back({L[i], R[i]});
  }
  sort(segs.begin(), segs.end(), [&](array<int, 2> a, array<int, 2> b) {
    return a[1] < b[1];
  });
  int ptr = 0;
  int k = (int) xs.size();
  fenwick<int> fenw(k);
  vector<int> nxt(n);
  for (int qq = 0; qq < (int) vec.size(); qq++) {
    int i = vec[qq].first;
    int t = vec[qq].second;
    int j = (int) (lower_bound(my[i].begin(), my[i].end(), t) - my[i].begin());
    while (ptr < (int) segs.size() && segs[ptr][1] < t) { 
      fenw.modify((int) (lower_bound(xs.begin(), xs.end(), segs[ptr][0]) - xs.begin()), +1);
      ptr += 1;
    }
    long long nd = dist[i][j];
    if (sz[i] < BLOCK) {
      for (int k = 0; k < j; k++) {
        int from = (int) (lower_bound(xs.begin(), xs.end(), my[i][k]) - xs.begin());
        int to = (int) (lower_bound(xs.begin(), xs.end(), my[i][j]) - xs.begin());
        nd = min(nd, dist[i][k] + (fenw.get(to - 1) - fenw.get(from)) * 1LL * T[i]);
      }
    } else {
      while (nxt[i] < (int) segs.size() && segs[nxt[i]][1] < t) {
        int idx = (int) (lower_bound(xs.begin(), xs.end(), segs[nxt[i]][0]) - xs.begin());
        AddRange(root[i], 0, k - 1, 0, idx - 1, T[i]);
        nxt[i] += 1;
      }
      int idx = (int) (lower_bound(xs.begin(), xs.end(), t) - xs.begin());
      nd = min(nd, Query(root[i], 0, k - 1, 0, idx));
      Modify(root[i], 0, k - 1, idx, dist[i][j]);
    }
    for (auto& p : g[i][j]) {
      int to = Y[p];
      int time = B[p];
      int idx = (int) (lower_bound(my[to].begin(), my[to].end(), time) - my[to].begin());
      dist[to][idx] = min(dist[to][idx], nd + C[p]);
    }
  }
  ptr = 0;
  sort(segs.begin(), segs.end(), [&](array<int, 2> a, array<int, 2> b) {
    return a[0] > b[0];
  });
  long long res = inf;
  for (int i = sz[n - 1] - 1; i >= 0; i--) {
    while (ptr < (int) segs.size() && segs[ptr][0] > my[n - 1][i]) {
      ptr++;
    }
    res = min(res, dist[n - 1][i] + ptr * 1LL * T[n - 1]);
  }
  if (res == inf) {
    return -1;
  } else {
    return res;
  }
}

Compilation message

train.cpp: In function 'long long int solve(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:170:8: warning: variable 'Count' set but not used [-Wunused-but-set-variable]
  170 |   auto Count = [&](int from, int to) {
      |        ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Correct.
2 Correct 1 ms 604 KB Correct.
3 Correct 2 ms 604 KB Correct.
4 Correct 2 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
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 19136 KB Correct.
2 Correct 217 ms 29520 KB Correct.
3 Correct 1 ms 348 KB Correct.
4 Correct 11 ms 9044 KB Correct.
5 Correct 0 ms 600 KB Correct.
6 Execution timed out 1074 ms 20676 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 19136 KB Correct.
2 Correct 217 ms 29520 KB Correct.
3 Correct 1 ms 348 KB Correct.
4 Correct 11 ms 9044 KB Correct.
5 Correct 0 ms 600 KB Correct.
6 Execution timed out 1074 ms 20676 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Correct.
2 Correct 1 ms 604 KB Correct.
3 Correct 2 ms 604 KB Correct.
4 Correct 2 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 424 ms 19136 KB Correct.
9 Correct 217 ms 29520 KB Correct.
10 Correct 1 ms 348 KB Correct.
11 Correct 11 ms 9044 KB Correct.
12 Correct 0 ms 600 KB Correct.
13 Execution timed out 1074 ms 20676 KB Time limit exceeded
14 Halted 0 ms 0 KB -