oj.uz

Submission #1038639

# Submission time Handle Problem Language Result Execution time Memory
1038639 2024-07-30T04:37:12 Z juicy Constellation 3 (JOI20_constellation3) C++17
35 / 100
 14 ms 9104 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5, inf = 1e9 + 7;

int n, m;
int a[N], c[N], tin[N], tout[N];
long long ft[N], dp[N];
array<int, 2> s[4 * N], buc[4 * N];
vector<array<int, 2>> pt[N];

void bld1(int id = 1, int l = 1, int r = n) {
  if (l == r) {
    s[id] = {-a[l], l};
    return;
  }
  int md = (l + r) / 2;
  bld1(id * 2, l, md);
  bld1(id * 2 + 1, md + 1, r);
  s[id] = min(s[id * 2], s[id * 2 + 1]);
}

void bld2(int id = 1, int l = 1, int r = n) {
  if (l == r) {
    buc[id] = {pt[l].back()[0], l};
    return;
  }
  int md = (l + r) / 2;
  bld2(id * 2, l, md);
  bld2(id * 2 + 1, md + 1, r);
  buc[id] = min(buc[id * 2], buc[id * 2 + 1]);
}

array<int, 2> qry(int u, int v, array<int, 2> *tree, int id = 1, int l = 1, int r = n) {
  if (u <= l && r <= v) {
    return tree[id];
  }
  int md = (l + r) / 2;
  if (v <= md) {
    return qry(u, v, tree, id * 2, l, md);
  }
  if (md < u) {
    return qry(u, v, tree, id * 2 + 1, md + 1, r);
  }
  return min(qry(u, v, tree, id * 2, l, md), qry(u, v, tree, id * 2 + 1, md + 1, r));
}

void pop(int i, int id = 1, int l = 1, int r = n) {
  if (l == r) {
    pt[l].pop_back();
    assert(pt[l].size());
    buc[id] = {pt[l].back()[0], l};
    return;
  }
  int md = (l + r) / 2;
  if (i <= md) {
    pop(i, id * 2, l, md);
  } else {
    pop(i, id * 2 + 1, md + 1, r);
  }
  buc[id] = min(buc[id * 2], buc[id * 2 + 1]);
}

void up(int i, long long x) {
  for (; i <= n; i += i & -i) {
    ft[i] += x;
  }
}

void up(int l, int r, long long x) {
  up(l, x);
  up(r + 1, -x);
}

long long qry(int i) {
  long long res = 0;
  for (; i; i -= i & -i) {
    res += ft[i];
  }
  return res;
}

int timer;

int dfs(int l, int r, int p) {
  int u = qry(l, r, s)[1];
  tin[u] = ++timer;
  long long sum = 0;
  if (l < u) {
    sum += dp[dfs(l, u - 1, a[u])];
  }
  if (u < r) {
    sum += dp[dfs(u + 1, r, a[u])];
  }
  dp[u] = sum;
  while (1) {
    auto x = qry(l, r, buc);
    if (x[0] > p) {
      break;
    }
    int v = x[1], c = pt[x[1]].back()[1];
    pop(x[1]);
    dp[u] = max(dp[u], sum + qry(tin[v]) + c);
  }
  tout[u] = timer;
  up(tin[u], tout[u], sum - dp[u]);
  return u;
}

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

  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  bld1();
  cin >> m;
  long long tot = 0;
  for (int i = 1; i <= m; ++i) {
    int x, y; cin >> x >> y >> c[i];
    pt[x].push_back({y, c[i]});
    tot += c[i];
  }
  for (int i = 1; i <= n; ++i) {
    pt[i].push_back({inf, 0});
    sort(pt[i].rbegin(), pt[i].rend());
  }
  bld2();
  cout << tot - dp[dfs(1, n, 1e9)];
  return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8836 KB Output is correct
4 Correct 1 ms 8844 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 1 ms 9052 KB Output is correct
8 Correct 1 ms 8796 KB Output is correct
9 Correct 1 ms 8796 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 1 ms 8796 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 4744 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 8796 KB Output is correct
17 Correct 1 ms 8796 KB Output is correct
18 Correct 1 ms 8796 KB Output is correct
19 Correct 1 ms 8876 KB Output is correct
20 Correct 1 ms 8792 KB Output is correct
21 Correct 1 ms 9048 KB Output is correct
22 Correct 1 ms 8792 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8836 KB Output is correct
4 Correct 1 ms 8844 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 1 ms 9052 KB Output is correct
8 Correct 1 ms 8796 KB Output is correct
9 Correct 1 ms 8796 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 1 ms 8796 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 4744 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 8796 KB Output is correct
17 Correct 1 ms 8796 KB Output is correct
18 Correct 1 ms 8796 KB Output is correct
19 Correct 1 ms 8876 KB Output is correct
20 Correct 1 ms 8792 KB Output is correct
21 Correct 1 ms 9048 KB Output is correct
22 Correct 1 ms 8792 KB Output is correct
23 Correct 3 ms 9052 KB Output is correct
24 Correct 2 ms 8796 KB Output is correct
25 Correct 2 ms 8796 KB Output is correct
26 Correct 2 ms 8796 KB Output is correct
27 Correct 2 ms 8796 KB Output is correct
28 Correct 2 ms 8796 KB Output is correct
29 Correct 3 ms 8796 KB Output is correct
30 Correct 3 ms 8796 KB Output is correct
31 Correct 2 ms 8796 KB Output is correct
32 Correct 3 ms 9052 KB Output is correct
33 Correct 2 ms 9052 KB Output is correct
34 Correct 2 ms 9052 KB Output is correct
35 Correct 2 ms 9052 KB Output is correct
36 Correct 2 ms 9052 KB Output is correct
37 Correct 3 ms 9052 KB Output is correct
38 Correct 2 ms 9048 KB Output is correct
39 Correct 3 ms 8796 KB Output is correct
40 Correct 3 ms 9052 KB Output is correct
41 Correct 2 ms 8912 KB Output is correct
42 Correct 2 ms 8796 KB Output is correct
43 Correct 3 ms 9104 KB Output is correct
44 Correct 2 ms 4952 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8836 KB Output is correct
4 Correct 1 ms 8844 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 1 ms 9052 KB Output is correct
8 Correct 1 ms 8796 KB Output is correct
9 Correct 1 ms 8796 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 1 ms 8796 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 4744 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 8796 KB Output is correct
17 Correct 1 ms 8796 KB Output is correct
18 Correct 1 ms 8796 KB Output is correct
19 Correct 1 ms 8876 KB Output is correct
20 Correct 1 ms 8792 KB Output is correct
21 Correct 1 ms 9048 KB Output is correct
22 Correct 1 ms 8792 KB Output is correct
23 Correct 3 ms 9052 KB Output is correct
24 Correct 2 ms 8796 KB Output is correct
25 Correct 2 ms 8796 KB Output is correct
26 Correct 2 ms 8796 KB Output is correct
27 Correct 2 ms 8796 KB Output is correct
28 Correct 2 ms 8796 KB Output is correct
29 Correct 3 ms 8796 KB Output is correct
30 Correct 3 ms 8796 KB Output is correct
31 Correct 2 ms 8796 KB Output is correct
32 Correct 3 ms 9052 KB Output is correct
33 Correct 2 ms 9052 KB Output is correct
34 Correct 2 ms 9052 KB Output is correct
35 Correct 2 ms 9052 KB Output is correct
36 Correct 2 ms 9052 KB Output is correct
37 Correct 3 ms 9052 KB Output is correct
38 Correct 2 ms 9048 KB Output is correct
39 Correct 3 ms 8796 KB Output is correct
40 Correct 3 ms 9052 KB Output is correct
41 Correct 2 ms 8912 KB Output is correct
42 Correct 2 ms 8796 KB Output is correct
43 Correct 3 ms 9104 KB Output is correct
44 Correct 2 ms 4952 KB Output is correct
45 Runtime error 14 ms 7004 KB Execution killed with signal 11
46 Halted 0 ms 0 KB -