Submission #365855

#	Time	Username	Problem	Language	Result	Execution time	Memory
365855		Kazalika	Two Dishes (JOI19_dishes)	C++14	100 / 100	7155 ms	273368 KiB

dishes

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1e6 + 5;
const ll inf = 1e18;

ll sgt[N << 2], add[N << 2];

void push(int t, int l, int r) {
  if (add[t]) {
    sgt[t] += add[t];
    if (l < r) {
      add[t << 1] += add[t];
      add[t << 1 | 1] += add[t];
    }
    add[t] = 0;
  }
}

void upd(int t, int l, int r, int x, ll val) {
  push(t, l, r);
  if (x < l || x > r)
    return;
  if (l == r) {
    sgt[t] = max(sgt[t], val);
    return;
  }
  int md = (l + r) >> 1;
  upd(t << 1, l, md, x, val);
  upd(t << 1 | 1, md + 1, r, x, val);
  sgt[t] = max(sgt[t << 1], sgt[t << 1 | 1]);
}

void add_range(int t, int l, int r, int x, int y, ll val) {
  push(t, l, r);
  if (l > y || r < x || l > r)
    return;
  if (l >= x && r <= y) {
    add[t] = val;
    push(t, l, r);
    return;
  }
  int md = (l + r) >> 1;
  add_range(t << 1, l, md, x, y, val);
  add_range(t << 1 | 1, md + 1, r, x, y, val);
  sgt[t] = max(sgt[t << 1], sgt[t << 1 | 1]);
}

ll get_max(int t, int l, int r, int x, int y) {
  push(t, l, r);
  if (l > y || r < x || l > r)
    return -inf;
  if (l >= x && r <= y)
    return sgt[t];
  int md = (l + r) >> 1;
  return max(get_max(t << 1, l, md, x, y), get_max(t << 1 | 1, md + 1, r, x, y));
}

int a[N], b[N];
ll s[N], t[N];
int p[N], q[N];
ll sa[N], sb[N];
map<pair<int, int>, ll> qq;



int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    cin >> a[i] >> s[i] >> p[i];
    sa[i] = (i ? sa[i - 1] : 0) + a[i];
  }
  for (int i = 0; i < m; ++i) {
    cin >> b[i] >> t[i] >> q[i];
    sb[i] = (i ? sb[i - 1] : 0) + b[i];
  }
  ll sum = 0;
  for (int i = 0; i < n; ++i) {
    if (sa[i] > s[i])
      continue;
    if (sa[i] + sb[m - 1] <= s[i])
      sum += p[i];
    else {
      int nw = upper_bound(sb, sb + m, s[i] - sa[i]) - sb;
      qq[{(i + 1) - 1, -nw - 1}] += p[i];
    }
  }
  for (int i = 0; i < m; ++i) {
    if (sb[i] > t[i])
      continue;
    if (sb[i] + sa[n - 1] <= t[i])
      sum += q[i];
    else {
      int nw = upper_bound(sa, sa + n, t[i] - sb[i]) - sa;
      sum += q[i];
      qq[{nw, -(i + 1)}] -= q[i];
    }
  }
  for (auto &pt : qq) {
    int y = -pt.first.second;
    ll val = pt.second;
    ll nw = get_max(1, 0, N - 1, 0, y - 1);
    upd(1, 0, N - 1, y, nw);
    add_range(1, 0, N - 1, 0, y - 1, val);
  }
  push(0, 0, N - 1);
  ll ans = sgt[1] + sum;
  cout << ans;
}

• 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: 17 / 17
• Subtask 8: 9 / 9