Submission #579284

#	Time	Username	Problem	Language	Result	Execution time	Memory
579284		lumibons	Two Dishes (JOI19_dishes)	C++17	74 / 100	6755 ms	203328 KiB

dishes

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll inf = 1LL << 60;

typedef ll sdata;

struct operation {
  ll add = 0, max = -inf;
};

sdata combine(sdata dl, sdata dr) {
  return max(dl, dr);
}

sdata calculate(operation o, sdata d) {
  return max(o.max, d + o.add);
}

operation merge(operation ot, operation ob) {
  return { ot.add + ob.add, max(ot.max, ob.max + ot.add) };
}

const int sn = 1 << 20;
sdata s[2 * sn];
operation o[sn];

void apply(int x, operation op) {
  s[x] = calculate(op, s[x]);
  if (x < sn)
    o[x] = merge(op, o[x]);
}

void push(int x) {
  apply(x << 1, o[x]);
  apply(x << 1 | 1, o[x]);
  o[x] = operation();
}

sdata query(int a, int b, int l = 0, int r = sn, int x = 1) {
  if (b <= l || r <= a)
    return -inf;
  if (a <= l && r <= b)
    return s[x];
  push(x);
  return combine(query(a, b, l, (l + r) / 2, x << 1), query(a, b, (l + r) / 2, r, x << 1 | 1));
}

void apply(int a, int b, operation op, int l = 0, int r = sn, int x = 1) {
  if (b <= l || r <= a)
    return;
  if (a <= l && r <= b)
    return apply(x, op);
  push(x);
  apply(a, b, op, l, (l + r) / 2, x << 1);
  apply(a, b, op, (l + r) / 2, r, x << 1 | 1);
  s[x] = combine(s[x << 1], s[x << 1 | 1]);
}

int n[2];
ll a[2][1000100], t[2][1000100], p[2][1000100];
vector<int> rem[1000100];

int main() {
  cin >> n[0] >> n[1];
  for (int j = 0; j < 2; j++)
    for (int i = 0; i < n[j]; i++)
      cin >> a[j][i] >> t[j][i] >> p[j][i], i > 0 ? a[j][i] += a[j][i - 1] : 0, t[j][i] -= a[j][i];
  ll p1 = 0;
  for (int i = 0; i < n[1]; i++)
    if (t[1][i] >= 0) {
      p1 += p[1][i];
      int j = upper_bound(a[0], a[0] + n[0], t[1][i]) - a[0];
      rem[j].push_back(i);
    }
  apply(0, n[1] + 1, { 0, p1 });
  for (int i = 0; i < n[0]; i++) {
    for (int j : rem[i])
      apply(j + 1, n[1] + 1, { 0, query(0, j + 1) });
    if (t[0][i] >= 0) {
      int j = upper_bound(a[1], a[1] + n[1], t[0][i]) - a[1];
      apply(j + 1, n[1] + 1, { 0, query(0, j + 1) });
      apply(0, j + 1, { p[0][i], -inf });
    }
    for (int j : rem[i])
      apply(0, j + 1, { -p[1][j], -inf });
  }
  cout << query(0, n[1] + 1) << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9