Submission #1206451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206451		abczz	Two Dishes (JOI19_dishes)	C++20	74 / 100	2101 ms	164888 KiB

dishes

#include <iostream>
#include <vector>
#include <array>
#include <map>
#define ll long long

using namespace std;

vector <array<ll, 2>> V[1000001];
map <ll, ll> diff;
ll n, m, psA[1000001], psB[1000001], A[1000001], B[1000001], P[1000001], Q[1000001];

void upd(ll x, ll y) {
  diff[x] += y;
  if (diff[x] < 0) {
    ll z = -diff[x], k;
    diff[x] = 0;
    auto it = next(diff.find(x));
    while (z && it != diff.end()) {
      auto nx = next(it);
      k = min(z, it->second);
      ll u = it->first;
      z -= k;
      diff[u] -= k;
      if (diff[u] == 0) diff.erase(it);
      else break;
      it = nx;
    }
  }
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> m;
  for (int i=0; i<n; ++i) {
    cin >> psA[i] >> A[i] >> P[i];
    if (i) psA[i] += psA[i-1];
    A[i] -= psA[i];
  }
  for (int i=0; i<m; ++i) {
    cin >> psB[i] >> B[i] >> Q[i];
    if (i) psB[i] += psB[i-1];
    B[i] -= psB[i];
  }
  for (int i=0; i<n; ++i) {
    if (A[i] < 0) continue;
    auto it = lower_bound(psB, psB+m, A[i]+1);
    A[i] = it-psB;
  }
  for (int i=0; i<m; ++i) {
    if (B[i] < 0) continue;
    auto it = lower_bound(psA, psA+n, B[i]+1);
    B[i] = it-psA;
    V[B[i]].push_back({i+1, Q[i]});
  }
  for (int i=0; i<=max(n, m); ++i) {
    bool ok = 0;
    for (auto [x, y] : V[i]) {
      if (!ok && 1 <= i && i <= n && A[i-1] >= 0 && x >= A[i-1]) {
        ok = 1;
        diff[0] += P[i-1];
        upd(A[i-1]+1, -P[i-1]);
      }
      upd(x, y);
    }
    if (!ok && 1 <= i && i <= n && A[i-1] >= 0) {
      diff[0] += P[i-1];
      upd(A[i-1]+1, -P[i-1]);
    }
  }
  ll f = 0;
  for (int i=0; i<=max(n, m); ++i) f += diff[i];
  cout << f << '\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