Submission #104653

#	Time	Username	Problem	Language	Result	Execution time	Memory
104653		IOrtroiii	Two Dishes (JOI19_dishes)	C++14	100 / 100	8938 ms	253064 KiB

dishes

#include <bits/stdc++.h>

using namespace std;

const int N = 1000100;
const long long inf = 1e18;

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

long long T[N << 2], lz[N << 2];

void push(int v,int l,int r) {
  if (lz[v]) {
    T[v] += lz[v];
    if (l < r) {
      lz[v << 1] += lz[v];
      lz[v << 1 | 1] += lz[v];
    }
    lz[v] = 0;
  }
}

void upd(int v,int l,int r,int x,long long y) {
  push(v, l, r);
  if (x < l || x > r) return;
  if (l == r) {
    T[v] = max(T[v], y);
    return;
  }
  int md = (l + r) >> 1;
  upd(v << 1, l, md, x, y);
  upd(v << 1 | 1, md + 1, r, x, y);
  T[v] = max(T[v << 1], T[v << 1 | 1]);
}

void add(int v,int l,int r,int L,int R,long long x) {
  push(v, l, r);
  if (L > r || R < l || L > R) return;
  if (L <= l && r <= R) {
    lz[v] = x;
    push(v, l, r);
    return;
  }
  int md = (l + r) >> 1;
  add(v << 1, l, md, L, R, x);
  add(v << 1 | 1, md + 1, r, L, R, x);
  T[v] = max(T[v << 1], T[v << 1 | 1]);
}

long long get(int v,int l,int r,int L,int R) {
  push(v, l, r);
  if (L > r || R < l || L > r) return -inf;
  if (L <= l && r <= R) return T[v];
  int md = (l + r) >> 1;
  return max(get(v << 1, l, md, L, R), get(v << 1 | 1, md + 1, r, L, R));
}

int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d %lld %d", a + i, s + i, p + i);
    sa[i] = sa[i - 1] + a[i];
  }
  for (int i = 1; i <= m; ++i) {
    scanf("%d %lld %d", b + i, t + i, q + i);
    sb[i] = sb[i - 1] + b[i];
  }
  long long sum = 0;
  for (int i = 1; i <= n; ++i) {
    if (sa[i] > s[i]) continue;
    else if (sa[i] + sb[m] <= s[i]) sum += p[i];
    else {
      int nw = upper_bound(sb + 1, sb + 1 + m, s[i] - sa[i]) - sb - 1;
      change[{i - 1, -nw - 1}] += p[i];
    }
  }
  for (int i = 1; i <= m; ++i) {
    if (sb[i] > t[i]) continue;
    else if (sb[i] + sa[n] <= t[i]) sum += q[i];
    else {
      int nw = upper_bound(sa + 1, sa + 1 + n, t[i] - sb[i]) - sa - 1;
      sum += q[i];
      change[{nw, -i}] -= q[i];
    }
  }
  for (auto p : change) {
    int x = p.first.first;
    int y = -p.first.second;
    long long val = p.second;
    long long nw = get(1, 0, m + 5, 0, y - 1);
    upd(1, 0, m + 5, y, nw);
    add(1, 0, m + 5, 0, y - 1, val);
  }
  printf("%lld\n", T[1] + sum);
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:92:9: warning: unused variable 'x' [-Wunused-variable]
     int x = p.first.first;
         ^
dishes.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~~
dishes.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %lld %d", a + i, s + i, p + i);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %lld %d", b + i, t + i, q + i);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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