제출 #1206401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206401		abczz	Two Dishes (JOI19_dishes)	C++20	74 / 100	2075 ms	164820 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;
  //cout << x << "a" << y << endl;
  if (diff[x] < 0) {
    ll z = -diff[x], k;
    diff[x] = 0;
    auto it = next(diff.find(x));
    while (z && it != diff.end()) {
      //cout << it->first << "?" << it->second << endl;
      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;
    //cout << i << " " << A[i] << " " << P[i] << endl;
  }
  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]});
    //cout << i << " " << B[i] << " " << Q[i] << endl;
  }
  for (int i=0; i<=max(n, m); ++i) {
    if (1 <= i && i <= n && A[i-1] >= 0) {
      diff[0] += P[i-1];
      //cout << i << " " << A[i-1] << endl;
      upd(A[i-1]+1, -P[i-1]);
    }
    for (auto [x, y] : V[i]) {
      upd(x, y);
      //cout << i << "*" << x << endl;
    }
    /*ll s = 0;
    for (int j=0; j<=max(n, m); ++j) {
      s += diff[j];
      cout << i << " " << j << " " << diff[j] << " " << s << endl;
    }*/
  }
  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