Submission #857890

#	Time	Username	Problem	Language	Result	Execution time	Memory
857890		rxlfd314	Two Dishes (JOI19_dishes)	C++17	100 / 100	4691 ms	218768 KiB

dishes

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using arl2 = array<ll, 2>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

#define chmax(a, b) a = a > (b) ? a : (b)
#define chmin(a, b) a = a < (b) ? a : (b)

constexpr int mxN = 1000001;
constexpr ll NINF = 0xc0c0c0c0c0c0c0c0;
int N, M;
ll A[mxN], B[mxN], P[mxN], Q[mxN], S[mxN], T[mxN];

ll dp[1001][1001];
void naive_dp() {
  memset(dp, 0xc0, sizeof(dp));
  dp[0][0] = 0;
  FOR(i, 0, N)
    FOR(j, 0, M) {
      if (i || j)
        dp[i][j] = max(i ? dp[i-1][j] + P[i] * (A[i] - S[i] <= -B[j]) : NINF, j ? dp[i][j-1] + Q[j] * (A[i] <= T[j] - B[j]) : NINF);
      cout << dp[i][j] << "\n "[j<M];
    }
  cout << '\n';
}

#define lc i << 1
#define rc i << 1 | 1
ll fp[mxN<<2], p[mxN<<2], lz_max[mxN<<2], lz_add[mxN<<2];
void push(int i) {
  auto apply = [&](int j) {
    fp[j] += lz_add[i];
    lz_add[j] += lz_add[i];
    lz_max[j] += lz_add[i];
    chmax(lz_max[j], lz_max[i]);
    chmax(fp[j], lz_max[i]);
    p[j] += p[i];
  };
  apply(lc);
  apply(rc);
  lz_max[i] = NINF;
  lz_add[i] = p[i] = 0;
}
void upd(int ql, int qr, ll v, int key, int i = 1, int tl = 0, int tr = M) {
  if (tl > qr || tr < ql)
    return;
  if (ql <= tl && tr <= qr) {
    if (!key)
      p[i] += v;
    else if (key < 2)
      lz_add[i] += v, lz_max[i] += v, fp[i] += v;
    else
      chmax(lz_max[i], v), chmax(fp[i], v);
    return;
  }
  push(i);
  int tm = tl + tr >> 1;
  upd(ql, qr, v, key, lc, tl, tm);
  upd(ql, qr, v, key, rc, tm+1, tr);
  fp[i] = max(fp[lc], fp[rc]);
}
ll qry(int ql, int qr, bool key = 0, int i = 1, int tl = 0, int tr = M) {
  if (tl > qr || tr < ql)
    return NINF;
  if (ql <= tl && tr <= qr)
    return key ? fp[i] + p[i] : fp[i];
  push(i);
  int tm = tl + tr >> 1;
  return max(qry(ql, qr, key, lc, tl, tm), qry(ql, qr, key, rc, tm+1, tr));
}
void print(int i = 1, int tl = 0, int tr = M) {
  if (tl == tr)
    cout << fp[i] + p[i] << "\n "[tl<M];
  else {
    push(i);
    int tm = tl + tr >> 1;
    print(lc, tl, tm);
    print(rc, tm+1, tr);
  }
}
#undef lc
#undef rc

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  // range update
  // 0: update transitions
  // 1: add P[i]
  // 2: range max update
  cin >> N >> M;
  FOR(i, 1, N)
    cin >> A[i] >> S[i] >> P[i], A[i] += A[i-1];
  memset(lz_max, 0xc0, sizeof(lz_max));
  priority_queue<arl2, vt<arl2>, greater<arl2>> pq;
  FOR(i, 1, M) {
    cin >> B[i] >> T[i] >> Q[i], B[i] += B[i-1];
    if (T[i] - B[i] >= 0) {
      pq.push({T[i] - B[i], i});
      upd(i, M, Q[i], 0);
    }
  }
#ifdef DEBUG
  naive_dp();
  print();
#endif
  
  FOR(i, 1, N) {
    int ind = upper_bound(B, B+M+1, S[i]-A[i]) - B - 1;
    vt<int> vec;
    while (size(pq) && pq.top()[0] < A[i]) {
      int j = pq.top()[1];
      vec.push_back(j);
      upd(j, M, -Q[j], 0);
      upd(j, M, Q[j], 1);
      pq.pop();
    }
    if (~ind) {
      vec.push_back(ind);
      upd(0, ind, P[i], 1);
    }
    sort(all(vec));
    for (int j : vec)
      upd(j, M, qry(0, j), 2);
#ifdef DEBUG
    print();
#endif
  }

  cout << qry(M, M, 1) << '\n';
}

Compilation message (stderr)

dishes.cpp: In function 'void upd(int, int, ll, int, int, int, int)':
dishes.cpp:65:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
dishes.cpp: In function 'll qry(int, int, bool, int, int, int)':
dishes.cpp:76:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
dishes.cpp: In function 'void print(int, int, int)':
dishes.cpp:84:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |     int tm = tl + tr >> 1;
      |              ~~~^~~~

• 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